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

11779번: 최소비용 구하기 2

11779번: 최소비용 구하기 2

🤔 문제분석

우선순위큐를 이용하여 문제를 해결하였는데요, 예전에 풀었던 유형이랑 비슷해서 문제를 쉽게 풀 수 있었습니다. 방문 경로를 구하는 로직은 거꾸로 우선순위큐를 역추적 하면됩니다. 말로는 어렵지만 코드를 보면 쉽게 이해 할 수 있습니다.

💻 코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize

n = int(input())
m = int(input())

edge = [[] for _ in range(n+1)]
reverse_edge = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, cost = map(int, input().split())
    edge[s].append((e, cost))
    reverse_edge[e].append((s, cost))
    
start, end = map(int, input().split())

queue = []
dp = [INF for _ in range(n+1)]

heapq.heappush(queue, (start, 0))
while queue:
    cur, cost = heapq.heappop(queue)
    
    if cost > dp[cur]:
        continue
    
    dp[cur] = cost
    
    for next, next_cost in edge[cur]:
        new_cost = next_cost + cost
        if dp[next] > new_cost:
            dp[next] = new_cost
            heapq.heappush(queue, (next, new_cost))
    
                
city = []
city.append(end)
cur = end
while cur != start:
    for prev, cost in reverse_edge[cur]:
        if dp[cur] == dp[prev] + cost:
            city.append(prev)
            cur = prev
            break

print(dp[end])
print(len(city))  
print(*reversed(city))

🎯 피드백 및 개선사항

다른사람들의 풀이를 보니 배열을 하나 만들고 이전에 방문했던 노드를 넣어두고 그 노드를 역추적 하여 문제를 해결 하신 분도 있어서 참고하였습니다~