[백준 11779번] 최소비용 구하기 2 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
import heapq
INF = sys.maxsize

N = int(input())
M = int(input())

graph = [[] for i in range(N+1)]

money = [INF]*(N+1)
route = [[] for i in range(N+1)]

for i in range(M):
  x1,x2,w = map(int,input().split())
  graph[x1].append((x2,w))

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

hq = []
heapq.heappush(hq,(0,start,0))

while hq:
  w,x,last = heapq.heappop(hq)
  
  if money[x] <= w:
    continue
    
  money[x] = w
  route[x] = route[last][:]
  route[x].append(last)
  for i in graph[x]:
      x1,w1 = i
      heapq.heappush(hq,(w+w1,x1,x))

print(money[goal])
print(len(route[goal]))
print(" ".join(map(str,route[goal][1:])),end=" ")
print(goal)

 

전형적인 다 익스트라 문제인데 최소비용만을 구하는 것이 아니라 최소비용을 갖기 위한 경로까지 출력해야 하는 문제이다.

 

다 익스트라의 heapq에 들어가는 tuple에 비용과 현 위치, 그리고 추가로 이전 위치까지 데이터로 넣어준 뒤, 비용 list와 함께 route list를 만들어, 비용이 초기화될 때마다 route를 이전 위치의 route로 초기화시켜주는 방식으로 해결하였다.

 

다 익스트라의 원리를 이해했다면 쉽게 풀 수 있는 문제이다.

 

 

오늘의 교훈) 알고리즘을 무지성으로 쓰지 말고 원리를 이해하자