[Python/파이썬] 백준 11779번: 최소비용 구하기 2

문제

풀이

다익스트라 알고리즘을 사용하되, 최단경로 값이 갱신될 때 그때의 노드 값도 함께 기록한다.

 

시작 노드가 1번 일 때,

 

1. 초기값

distance : 1번 노드에서 다른 노드로 갈 수 있는 최단 경로

1	2	3	4	5	6
0	4	2	INF	INF	INF

 

nearnest 값 : 방문한 노드({1}) 중에서 가장 가까운 노드

1	2	3	4	5	6
1	1	1	1	1	1

 

2. 갱신

distance : 1번 노드에서 n번 노드로 가는 비용보다 1~3, 3~n으로 가는 비용이 더 작으면 갱신

1	2	3	4	5	6
0	4	2	INF	6 (갱신)	INF

 

nearnest 값 : 방문한 노드({1, 3}) 중에서 가장 가까운 노드

1	2	3	4	5	6
1	1	1	1	3 (갱신)	1

 

3. 2번 반복

문제에서 주어진 도착 노드가 5라고 하면

5의 가장 가까운 노드를 구하고, 그 노드의 가장 가까운 노드를 구하는 과정을

시작 노드가 나올 때까지 반복하면 된다. 이 과정을 역으로 하면 최단 경로.

 

코드

import sys, heapq
input = sys.stdin.readline

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

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

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

# 가장 가까운 노드를 기록
nearnest = [start] * (n + 1)
distance = [1e9] * (n + 1)

q = [(0, start)]
while q:
    dist, now = heapq.heappop(q)
    if dist > distance[now]:
        continue
    
    for next, nextDist in graph[now]:
        cost = nextDist + dist
        if cost < distance[next]:
            distance[next], nearnest[next] = cost, now
            heapq.heappush(q, (cost, next))
    
ans = []
tmp = end
while tmp != start:
    ans.append(str(tmp))
    tmp = nearnest[tmp]

ans.append(str(start))
ans.reverse()

print(distance[end])
print(len(ans))
print(" ".join(ans))

 

마무리

학교 알고리즘 수업에서 했던 과제라 쉽게 풀 수 있었다 ㅎㅎ