[백준/Python] 5972. 택배 배송

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

 

📌  문제 접근

1번 헛간에서 출발해 N번 헛간까지 이동하는 과정에서, 각 길을 지날 때마다 소에게 줄 여물의 비용이 발생한다. 목표는 여물의 총합이 최소가 되는 경로를 찾는 것이다. 즉, 최단 경로 문제로 풀면 된다.

• 간선의 가중치가 모두 양수이므로 다익스트라 알고리즘을 적용할 수 있다
• N과 M의 범위가 1 ~ 50,000이기때문에 우선순위 큐를 이용하여 구현했다.

[Python] 다익스트라(Dijkstra) 알고리즘

[Python] 다익스트라(Dijkstra) 알고리즘

 

 

---

🔍 문제 풀이

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

# N: 헛간 수(정점), M: 길의 수(간선)
N, M = map(int, input().split())

# 인접 리스트 그래프
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))  # 양방향

# 다익스트라 거리 배열
INF = float('inf')
dist = [INF] * (N + 1)
dist[1] = 0 # 시작은 1번

# 우선순위 큐 (현재까지 비용, 정점)
pq = [(0, 1)]

while pq:
    cost, u = heappop(pq)

    # 이미 더 짧은 경로가 있다면 스킵
    if cost > dist[u]:
        continue

    for v, w in graph[u]:
        new_cost = cost + w
        if new_cost < dist[v]:
            dist[v] = new_cost
            heappush(pq, (new_cost, v))

print(dist[N])