백준 11779번 : 최소비용 구하기 2 (Python)

출처 : https://www.acmicpc.net/problem/11779

import heapq

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m) :
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
start, end = map(int, input().split())

INF = int(1e8)
dist = [[INF, 0] for _ in range(n+1)]
def dijkstra(start, end) :
    dist[start][0] = 0
    pq = []
    heapq.heappush(pq, (dist[start][0], start))
    while pq :
    	# 현 정점까지 최소비용, 현 정점
        dist_now, now = heapq.heappop(pq)
        # 이미 저장된 비용이 더 작으면 갱신할 필요 없음
        if dist[now][0] < dist_now :
            continue
        # 현 정점과 이웃한 정점 탐색
        for near, dist_now_near in graph[now] :
            # 현 정점을 거쳐서 이웃 정점으로 가는 비용이 더 작으면 갱신
            if dist[near][0] > dist_now + dist_now_near :
                dist[near][0] = dist_now + dist_now_near
                dist[near][1] = now
                heapq.heappush(pq, (dist[near][0], near))
    return dist[end][0]

print(dijkstra(start, end))

route = [end]
# 도착점부터 거슬러 올라가며 경로 탐색
while True :
    now = route[-1]
    before = dist[now][1]
    route.append(before)
    if before == start :
        print(len(route))
        print(*route[::-1])
        break

최소비용을 구하는 것은 일반적인 다익스트라 알고리즘을 활용하면 된다.

다만 이 문제에서는 경로까지 구해야 하므로, 비용을 저장하는 dist 배열에 '현 정점에 최소비용으로 도달할 때 직전에 방문한 정점'을 같이 저장한다.

코드에서는 now를 기준으로 인접한 near까지의 비용을 갱신하는데,

만약 near까지의 비용이 갱신되었다면 직전에 now를 방문했으므로 dist[near]에 now도 함께 저장하는 것이다.

마지막으로 도착점부터 거슬러올라가며 경로를 저장하고 출발점에 도달했으면 경로의 개수와 경로(저장된 경로의 역순)을 출력한다.