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

문제

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

분석

n개의 도시가 있고, m개의 버스 정보가 주어지면, A에서 B도시로 가는데 드는 최소비용과 경로를 출력하는 문제이다.

일단 이 문제는 가중치가 있는 그래프에서 최소비용을 구하는 문제이므로 다익스트라 알고리즘을 바로 떠올리면 된다. 추가적으로 경로를 알아내야 되는데, 방법은 다음과 같다.
현재 도시의 바로 직전의 도시를 저장해두는 dictionary를 활용하면 된다.
nxt에 가는 방법이 갱신이 될 때 path[nxt] = now 로 바로 직전 도시를 갱신해준다.
이렇게 다익스트라를 진행하고 난 후에, b에서 부터 a까지 path를 거꾸로 역추적하면 경로를 구할 수 있다. (리스트에 넣고 뒤집기)

코드

해결언어 : Python

import sys
input = sys.stdin.readline
INF = sys.maxsize
from heapq import heappush, heappop
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, d = map(int, input().split())
    graph[s].append((e, d))
a, b = map(int, input().split())

def dijkstra(src, dst):
    dist = [INF]*(n+1)
    dist[src] = 0
    path = {}
    pq = []
    heappush(pq, (0, src))
    while pq:
        now_d, now = heappop(pq)
        if dist[now] < now_d:
            continue
        for nxt, nxt_d in graph[now]:
            if dist[nxt] > now_d + nxt_d:
                path[nxt] = now
                dist[nxt] = now_d + nxt_d
                heappush(pq, (dist[nxt], nxt))
    return dist[dst], path

mn_cost, path = dijkstra(a, b)
lst = [b]
while path[b] != a:
    lst.append(path[b])
    b = path[b]
lst.append(a)
lst = lst[::-1]
print(mn_cost)
print(len(lst))
print(*lst)

끝으로..

기본 개념인 다익스트라에 경로추적을 하는 법까지 배울 수 있어서 좋았다.