문제

입력

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

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다. 경로가 여러가지인 경우 아무거나 하나 출력한다.

입력 예시 1

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

출력 예시 1

4
3
1 3 5

문제 이해

기본적인 다익스트라 구현문제에 경로 추적을 더한 개념이다. 경로 추적을 하기 위해서는 딕셔너리를 사용한다. 딕셔너리의 키 값을 배열처럼 노드 번호를 넣는다. 이 문제에서는 1번부터 노드가 시작이기에 1번부터 N+1까지 반복하며 N개의 키 값을 만든다.
기존의 다익스트라 알고리즘의 distance 리스트가 갱신이 될때 최단 경로가 수정이 될 수 있기 때문에 경로도 갱신해줘야 한다. "딕셔너리[부모노드 값] = 자식노드 번호" 처럼 부모노드 키 값에 자식노드 값을 넣어준다.

참고한 블로그
https://studyandwrite.tistory.com/381
이 블로그에서 정말 깔끔하게 역추적에 대해서 설명한다.

경로 역추적

# 경로 역추적
    route = [] # 경로를 넣을 리스트

    now = end_node 
    while now != start_node:
        route.append(now) # 값을 넣고 이전 경로를 now에 넣는다
        now = parents[now]
    route.append(start_node)

    # 역추적이므로 route에 반대로 들어갔기 때문에 역으로 정렬
    route.reverse()

다익스트라를 모두 돌린 후에 parents 딕셔너리에는 경로가 들어가 있다. 마지막 도착 노드 값을 키 값으로 넣으면 부모노드의 값이 나온다. 이를 이용하여 위처럼 반복문으로 now를 end_node에서부터 갱신하면서 추적한다. 반복문이 끝나면 start_node도 경로에 넣고, 역추적을 해서 경로가 반대로 저장되었기에 경로를 뒤집어 준다.

코드

# 백준 11779번 최소비용 구하기 2

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

# Import defaultdict
from collections import defaultdict

# Function Dijkstra
def Dijkstra(cur_cost, start_node):
    global cost, parents

    # parents 배열 초기화
    for i in range(1, N+1):
        parents[i] = None

    pq = PriorityQueue()
    pq.put([cur_cost, start_node])
    cost[start_node] = 0 # 시작점 비용 0

    while not pq.empty():

        cur_cost, cur_node = pq.get()

        # 어차피 갱신이 안될 값이 무의미한 반복문을 피하기 위해
        if cur_cost > cost[cur_node]:
            continue

        for adj_node, adj_cost in adj_list[cur_node]:
            
            temp_cost = cur_cost + adj_cost
            # 갱신 조건이고 아래가 갱신 할 값, 갱신할떄 부모노드를 넣어준다.
            if temp_cost < cost[adj_node]:
                cost[adj_node] = temp_cost
                pq.put([temp_cost, adj_node])
                parents[adj_node] = cur_node # 자식노드 키에 값은 부모 노드

    # 경로 역추적
    route = [] # 경로를 넣을 리스트

    now = end_node 
    while now != start_node:
        route.append(now) # 값을 넣고 이전 경로를 now에 넣는다
        now = parents[now]
    route.append(start_node)

    # 역추적이므로 route에 반대로 들어갔기 때문에 역으로 정렬
    route.reverse()
    return route
    
# 0. 입력 및 초기화
INF = int(1e12)

N = int(input())
M = int(input())
cost = [INF] * (N+1)

# 1. Create adj_list
adj_list = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, t = map(int, input().split())
    adj_list[a].append([b, t])

start_node, end_node = map(int, input().split())

# 경로를 역추적할 딕셔너리리
parents = defaultdict()

# 2. Excute Dijkstra
route = Dijkstra(0, start_node) # cur_cost, start_node

# 3. Print result
print(cost[end_node])
print(len(route))
print(" ".join(map(str, route)))