[백준/Python] 최단경로

[백준/Python] 최단경로

728x90

https://www.acmicpc.net/problem/1753

from collections import defaultdict import sys, heapq input = sys.stdin.readline V, E = map(int, input().split()) # 정점, 간선 개수 start = int(input()) # 시작 노드 graph = defaultdict(list) # 방향 그래프 dist = [sys.maxsize for _ in range(V+1)] # 최단 거리 리스트 # 간선 정보 입력받기 for _ in range(E): u, v, w = map(int, input().split()) graph[u].append((v, w)) # 다익스트라 메서드 def dijkstra(start): queue = [] # 우선순위 큐 dist[start] = 0 # 시작 노드 거리는 0 heapq.heappush(queue, (0, start)) # 꼭 (거리, 노드)로 삽입해야 함 while queue: cur_dist, node = heapq.heappop(queue) # 현재 노드의 거리, 현재 노드 if cur_dist > dist[node]: # 현재 노드의 거리가 최단거리 리스트의 값보다 크면 넘어감 continue for adj_node, adj_dist in graph[node]: # 그렇지 않다면 현재 노드와 연결된 노드 가져와서 cost = cur_dist + adj_dist # 거리 계산 if cost < dist[adj_node]: # 계산한 거리가 최단거리 리스트의 값보다 작다면 dist[adj_node] = cost # 거리 수정 heapq.heappush(queue, (cost, adj_node)) # 큐에 삽입 dijkstra(start) # 다익스트라 수행 # 결과 출력 for i in range(1, V+1): if dist[i] == sys.maxsize: # 경로가 없는 경우 print('INF') else: # 경로가 있다면 최단 거리 출력 print(dist[i])

1. 필요한 정보를 입력받고 필요한 변수를 생성한다.

2. 다익스트라를 수행한다.

2-1. 우선순위 큐를 생성하고 시작노드의 거리는 0으로 만든다. 큐에 시작 노드를 삽입하는데 꼭 (거리, 노드) 순으로 넣어야 한다.

2-2. 큐에 값이 없을 때까지 다음을 반복한다.

2-3. 큐에서 현재 노드를 가져온다. 현재 노드의 거리가 최단거리 리스트의 값보다 크면 비교할 것도 없으므로 넘어간다.

2-4. 그렇지 않다면 현재 노드와 연결된 노드를 가져온다. 연결된 노드의 최단 거리를 계산하고 그 거리가 최단거리 리스트의 값보다 작다면 거리를 수정한 후 큐에 삽입한다.

3. 결과를 출력한다.

3-1. 경로가 없는 경우 INF를 출력하고 그렇지 않다면 최단 거리를 출력한다.

728x90

from http://soohyun6879.tistory.com/234 by ccl(A) rewrite - 2021-11-19 17:26:25