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

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

11779번: 최소비용 구하기 2

 

import sys
import heapq
input = sys.stdin.readline


def getMinCostAndPath(start, end):
    dp = [float('inf') for _ in range(n+1)]
    todo = [(0, start, [start])]

    while todo:
        curCost, curNode, curPath = heapq.heappop(todo)

        # 우선순위큐로 꺼내므로 최소 비용이 드는 루트를 가장 먼저 방문함
        if curNode == end:
            return curCost, curPath

        if dp[curNode] < curCost:
            continue

        for adjNode, adjCost in graph[curNode]:
            nextCost = curCost + adjCost

            if nextCost < dp[adjNode]:
                dp[adjNode] = nextCost
                heapq.heappush(todo, (nextCost, adjNode, curPath + [adjNode]))


if __name__ == '__main__':
    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))

    start, end = map(int, input().split())
    minCost, path = getMinCostAndPath(start, end)

    print(minCost)
    print(len(path))
    print(*path)

 

다익스트라 알고리즘을 살짝 변형하면 된다. 우선순위큐(todo)에 지금까지 방문했던 노드를 리스트로 기록하는 것을 더해주면 된다.

또, whlie문에서 탐색을 하면서, 현재 노드가 도착 노드와 같을 경우 바로 리턴해준다. 이렇게 해도 되는 이유는, 우선순위큐를 통해 cost가 적은 것부터 탐색을 하기 때문이다.