[Python] 백준 / gold / 11779 : 최소비용 구하기 2

문제 링크 : https://www.acmicpc.net/problem/11779

다익스트라 알고리즘 문제. 이 문제는 최단 거리 뿐만 아니라 최단 경로까지 구해줘야 된다. 경로를 구해보는 건 처음이었는데, 다익스트라 알고리즘 흐름을 정확히 이해했다면 어렵지 않은 것 같다. 다익스트라는 우선순위 큐에 노드들을 삽입하며 최단거리를 갱신하는 알고리즘이기 때문에, 그 큐에 경로를 저장해주면서 알고리즘을 수행하기만 하면 된다.

기억할 것 :
최단 경로를 구할 때는 큐에 경로를 추가해서 삽입하면 된다.

파이썬 코드

import sys
import heapq
INF = 987654321
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    # 출발 노드, 도착 노드, 비용
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))


def dijkstra(start, end):
    # [거리, 지나온 경로]
    distance = [[INF, []] for _ in range(N + 1)]
    distance[start] = [0, [start]]

    q = []
    # (거리, 노드, 지나온 경로)
    heapq.heappush(q, (0, start, [start]))

    while q:
        dist, now, path = heapq.heappop(q)
        if distance[now][0] < dist:
            continue

        for node, d in graph[now]:
            cost = dist + d

            if cost < distance[node][0]:
                distance[node][0] = cost
                distance[node][1] = path + [node]
                q.append((cost, node, path + [node]))

    print(distance[end][0])
    print(len(distance[end][1]))
    for x in distance[end][1]:
        print(x, end=' ')


S, E = map(int, sys.stdin.readline().split())
dijkstra(S, E)