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

최소비용 구하기 2

🔍 알고리즘 분류

• 다익스트라

💡 문제 풀이

1. 노드에 도착하기 직전 노드를 저장하는 prev 배열 생성
2. 다익스트라 진행하면서 prev[현재노드] = 이전노드 저장
3. 다익스트라 진행 완료 후, 도착지점부터 출발지점까지 역추적하며 경로 생성

📄 코드

• Python

import heapq

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())

distance = [int(1e9)] * (n + 1)
prev = [0] * (n + 1) # 이전 경로 기록

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                prev[i[0]] = now
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
print(distance[end])

# 최단경로 역추적
path = []
cur = end
while cur != start:
    path.append(cur)
    cur = prev[cur]
path.append(start)
path.reverse()
print(len(path))
answer =  " ".join(map(str,path))
print(answer)