[Python] 백준 11779번 최소비용 구하기2

문제

11779번: 최소비용 구하기 2

입력

• 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
• 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

• 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
• 둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.
• 셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.

입력 예제

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

출력 예제

4
3
1 4 5

문제 풀이

• 다익스트라 알고리즘 수행 중 최단 경로를 갱신하는 부분에서 부모 노드 값도 갱신
• 도착지부터 출발지부터 거슬러 올라가면서 노드 번호 차례대로 넣기
• 도착지부터 출발지까지의 경로가 저장 되어있으므로, 출발지부터 출력하기 위해서 리스트 뒤집기
• 경로 길이와 노드번호 차례대로 출력

최단 경로가 여러 개 일 수 있어 출력 값으로 명시되어 있는 1 3 5와 코드를 실행했을 때 나오는 1 4 5가 모두 정답코드가 될 수 있다는 점에서 틀린 줄 알고 해맸다 ㅠ

코드

import heapq
import sys
INF = int(1e9)
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
parents = [0] * (n + 1) # 이동경로 저장
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b, c))
start, end = map(int,input().split())

def dijkstra(start):
    q = []
    # 비용, 노드
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                parents[i[0]] = now # 부모노드 저장
                heapq.heappush(q,(cost,i[0]))

dijkstra(start)
print(distance[end])

# 이동경로에 도착지 삽입
path = [end]
now = end
while start != now:
    now = parents[now]
    path.append(now)

# 도착경로부터 저장된 경로이므로 리스트 뒤집기
path.reverse()
print(len(path))
for i in path:
    print(i, end=' ')