[백준/Python] 최단경로

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

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를 출력하고 그렇지 않다면 최단 거리를 출력한다.