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

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

 

코드

import heapq
import sys
INF = int(1e9)

input = sys.stdin.readline

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

graph = [[] for _ in range(n+1)]

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

a, b = map(int, input().split())

dist = [INF] * (n+1)
prev_node = [0] * (n+1)    # 최단 경로 출력을 위한 변수

def dijkstra(a):
    q = []
    heapq.heappush(q, (0, a))
    dist[a] = 0
    while q:
        cost, now = heapq.heappop(q)
        if dist[now] < cost:
            continue
        for i in graph[now]:
            if dist[i[0]] > i[1] + cost:
                dist[i[0]] = i[1] + cost
                prev_node[i[0]] = now    # now -> i[0]
                heapq.heappush(q, (i[1] + cost, i[0]))

dijkstra(a)
print(dist[b])

path = [b]
now = b
while now != a:
    now = prev_node[now]
    path.append(now)

# now -> i[0] 순으로 경로가 이어질 때, prev_node[i[0]] = now 형태로 저장했기 때문에
# path에는 경로 역순으로 저장이 된다.
# 따라서, 경로를 뒤집어서 출력해주어야 한다.
path.reverse()

print(len(path))
print(' '.join(map(str, path)))

'''
n개의 도시, m개의 버스
A에서 B로 가는 버스 비용 최소화
'''

 

접근 방법

- 전형적인 다익스트라 문제 유형임을 아는 것은 어렵지 않았다

- 최소 비용을 출력 이외로, 경로에 포함된 도시 개수와 경로 자체를 출력하는게 포인트였던 문제인 듯?

 

배운 점

- 경로에 포함된 도시 개수와 경로 자체를 출력하기 위해서, prev_node 변수 사용

- a → b 로 이동하는 경우, prev_node[b] = a 형태로 저장

- 끝 노드부터 시작해서 출발 노드로 저장되기 때문에 뒤집어서 출력

- 리스트 뒤집기 : .reverse() 함수 사용

 

참고 자료

https://velog.io/@yoopark/baekjoon-11779