본문 바로가기

Algorithm/Shortest Way

 (7)
숨바꼭질 문제 유형 분석 및 구현 이 문제도 결과적으로 봐야한다. 결과적으로 한 노드에서 어떠한 노드로 가는데 가장 멀리있는 노드들 중에 번호가 작은 노드를 출력하는 문제이다. 처음에는 헷갈렸던 적도 있는 것 같다. 모든 노드와 노드사이의 최단 경로를 구해야하나라고 생각했다. 하지만 최단경로 문제들은 결과적으로 생각해야 한다. 결과적으로 1번 헛간과 가장 먼 거리를 찾는 경우이므로 다익스트라 알고리즘을 이용한다. 주의할 점은 양방향 통로라는 점이다. 따라서 입력받을 때, 두 노드 모두 경로 처리해야한다. 코드 import heapq n, m = map(int, input().split()) INF = int(1e9) graph = [[] for _ in range(n+1)] for i in range(m): a,..
화성 탐사 유형 파악 및 구현 이 문제는 우선, 한 노드에서 다른 노드로 가는 최단 경로를 구하는 문제이다. 따라서, 다익스트라 알고리즘을 통해 해결한다. 모든 노드에 대해서 첫번째 노드와의 최단경로를 구하면서 마지막 노드까지가서 결과적으로는 첫노드와 마지막노드의 최단경로를 구하는 것이다. 아래의 distance 배열은 노드 [0, 0]과의 거리를 의미한다. 코드 import heapq n = 7 graph = [ [9, 0, 5, 1, 1, 5, 3], [4, 1, 2, 1, 6, 5, 3], [0, 7, 6, 1, 6, 8, 5], [1, 1, 7, 8, 3, 2, 3], [9, 4, 0, 7, 6, 4, 1], [5, 8, 3, 2, 4, 8, 3], [7, 4, 8, 4, 8, 3, 4] ] INF = in..
정확한 순위 유형 파악 및 구현 이 문제는 B의 성적이 A의 성적이 높다 와 같은 정보들이 주어진다. 이를 활용해 성적 순위를 알 수 있는 학생의 수를 출력하는 것이다. 예를 들어, 5는 1보다 성적이 높다 4는 3보다 성적이 높다 2는 4보다 성적이 높다 6는 4보다 성적이 높다 2는 5보다 성적이 높다 5는 4보다 성적이 높다 라는 정보가 주어진다고 가정할 때, 순위를 알 수 있는 학생의 수를 구하는 것이다. 이를 해결하기 위한 전제 조건은 다음과 같다. "A가 B보다 높은지, B가 A보다 높은지 모르겠으면 비교가 불가능한 쌍이 된다" 이는 정확히 순위를 구하는 것이 아닌 순위를 알 수 있는 학생의 수를 구하는 문제이기에 가능하다. 이를 구현할때는 플로이드 워셜 알고리즘을 통해 모든 학생에서 모든 학생으로 가는 ..
플로이드 유형 파악 및 구현 이 문제는 플로이드-워셜 알고리즘으로 간단히 구현 가능하다. 다만, 이 문제를 풀면서 정확히 정리해야함을 느꼈다. 쉬운문제인만큼 꼼꼼히 봐야한다. Problems - 간선별로 양방향 노드가 연결된게 아닌데 처리해버림 - 시작노드와 도착노드를 연결하는 노선은 하나가 아닐 수 있다라는 조건을 놓침 - INF인 경우 0처리 안함. 코드 INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(graph[a][b], c) for i in range(1, n+1..
전보 유형 파악 이 문제는 특정 노드에서 다른 모든 노드로 갈 때 최단 경로를 구하는 문제이다. 다익스트라 알고리즘이 적합하다. 내 개인적인 생각으로는 최단 경로 알고리즘들은 그냥 적용하면 된다. 코드 import heapq n, m, c = 3, 2, 1 graph = [ [], [[2, 4], [3, 2]], [], [] ] INF = int(1e9) distance = [INF]*(n+1) distance[1] = 0 q = [] heapq.heappush(q, [0, 1]) while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for i in graph[now]: next_node = i[0] next_dist = i[1] di..
미래 도시 유형 파악 이 문제는 간단하다. a에서 b 그리고 b에서 c로의 이동을 다뤘다. 즉, 모든 경로에 대한 최단 경로가 필요하므로 최단 경로 알고리즘 중에서도 플로이드 워셜 알고리즘을 사용한다. 특징 적으로 3단 반복문을 사용하면 된다. 코드 n, m = map(int, input().split()) INF = 1e9 graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 x, k = map(int, input().split()) for i in range(1, n+1): graph[i][i] = 0 for a in range(1, n+1)..
Shortest Way - Concept 해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. - 한 지점에서 다른 특정 지점까지의 최단경로를 구해야 하는 경우 - 모든 지점에서 다른 모든 지점까지의 최단경로를 구해야하는 경우 종류 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - ex) 노드1 to 노드 2, 3, 4, 5 - 시간복잡도 : O(ElogV) - 우선순위 큐 (heapq), distance 테이블 활용 플로이드 워셜 알고리즘 - 모든 노드에서 출발하여 모든 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - ex) 노드1, 2, 3, 4, 5 to 노드 1, 2, 3, 4, 5 - 시간 복잡도 : O(N**3) - 3중 for문 사용 - 비교..

티스토리툴바