백준 11779 최소비용 구하기 2

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/11779

이 문제는 그래프가 주어져 있을 때, 시작 노드와 끝 노드를 입력받고, 시작 노드에서 끝 노드로 가는 최단 거리를 구하는 문제이며, 추가로 최단 거리로 가는 경로까지 구해주어야 하는 문제이다.

풀이

난이도 : GOLD III

이 문제는 전형적인 최단 경로 문제로 처음에 보자마자 다익스트라 알고리즘을 떠올렸다.
이 문제의 특별한 점은 최단 거리를 구하면서 그 최단 거리로 가는 최단 경로까지 같이 구해주어야 한다는 점이다.

따라서 다익스트라 알고리즘을 사용할 때, 경로까지 기억할 수 있도록 코드를 수정해주었다.(코드에서 history)
-> 우선순위 큐에 데이터로 history 부분을 추가하였고, distance가 바뀔 때마다 history에 대해서도 같이 업데이트를 해주었다.

✔ 주의할 점

• 이 문제는 input 양이 많으므로 sys.stdin.readline으로 입력받아야 한다.

코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
m = int(input())

distance = [int(1e9)] * (n + 1)
graph = [[] for _ in range(n + 1)]
# 방문 경로 기록
historys = [[] for _ in range(n + 1)]

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

# 다익스트라 (history에 방문 경로를 기록)
def dijkstra(start):
    q = []
    distance[start] = 0
    heapq.heappush(q, (start, 0, [start]))

    while q:
        x, dist, history = heapq.heappop(q)

        if distance[x] < dist:
            continue

        for i in graph[x]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                historys[i[0]] = history + [i[0]]
                heapq.heappush(q, (i[0], cost, history + [i[0]]))

start, end = map(int, input().split())
dijkstra(start)

print(distance[end])
print(len(historys[end]))
for i in range(len(historys[end])):
    if i == len(historys[end]) - 1:
        print(historys[end][i])    
    else:
        print(historys[end][i], end=" ")