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

문제 

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

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

 

난이도

골드3

 

내 코드

import sys
import heapq

def dijstra(start) :
    dp = [float('inf')] * (n+1)
    dp[start] = 0
    city = [[] for _ in range(n+1)]
    queue = []
    heapq.heappush(queue, (0,start))

    while queue :
        nowCost, nowNode = heapq.heappop(queue)

        if nowCost > dp[nowNode] :
            continue

        for neighbor, weight in cost[nowNode] :
            dis = nowCost + weight
            if dis < dp[neighbor] :
                dp[neighbor] = dis
                city[neighbor] = []
                for x in city[nowNode] :
                    city[neighbor].append(x)
                city[neighbor].append(nowNode)
                heapq.heappush(queue, (dis, neighbor))

    city[end].append(end)
    return dp[end], city[end]

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
cost = [[] for _ in range(n+1)]
for _ in range(m) :
    a, b, c = map(int,sys.stdin.readline().split())
    cost[a].append((b,c))
start, end = map(int,sys.stdin.readline().split())

answerCost, answerPath = dijstra(start)
print(answerCost)
print(len(answerPath))
print(*answerPath)

 

풀이과정

다이크스트라 알고리즘을 사용해서 풀었다.

기본 다이크스트라 알고리즘을 사용하면 출발 노드로부터 각각 노드로의 최소비용이 나온다.

거기에 경로를 어떤 식으로 찾아줘야하나 고민했다. 

다이크스트라 교안을 보며 생각해낸 방법은 노드마다 각각의 최단 경로를 담을 리스트(city)를 만들어두고, DP 가 업데이트 되는 순간에 최단 경로 정점(city[nowNode])의 경로로 바꿔주고 거기에 최단 경로 정점(nowNode)도 추가해주는것이다.

dp가 업데이트 됐다는건 최단 경로의 정점에서부터 그 경로로 가는게 기존보다 빠르단 뜻이기 때문이다.