백준 11779 : 최소비용 구하기 2 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(start,end):

    global visit

    heap=[] ; heapq.heappush(heap,(0,start))
    dp=[INF]*(N+1) ; dp[start]= 0


    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:
            next_value+=value

            if next_value < dp[next_node]:

                dp[next_node]=next_value
                visit[next_node]=node
                heapq.heappush(heap,(next_value,next_node))

    print(dp[end])

INF=int(1e12)
N=int(input())
M=int(input())

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

    A,B,C=map(int,input().split())
    graph[A].append((C,B))

start,end=map(int,input().split())
visit = [0]*(N+1)  # 모든 경로를 담는 리스트.

Dijkstra(start,end)

Answer=[] ; tmp=end

while tmp!=start:

    Answer.append(tmp)
    tmp=visit[tmp]

Answer.append(start)

print(len(Answer))
print(*Answer[::-1])

📌 어떻게 접근할 것인가?

최소비용 구하기 1 문제에서 다익스트라로 최단경로를 구했을때 어떤경로를 이동했는지를 찾는 문제입니다.

visit=[0]*(N+1) 로 배열을 만들어 준 다음에 만약 이동이 가능한 지점이 나타나면

이동할 지점에 현재 노드번호를 저장합니다.

그리고 다익스트라가 끝난후에 도착점을 tmp 로 잡으면 이전에 이동했던 값은 visit[tmp] 가 되므로 다시 되돌아가면서 이동했던 경로를 저장합니다.

그리고 다시 역순으로 출력하면 이동했던 경로를 찾을 수 있습니다.