[백준] 5972. 택배 배송 풀이 (Python)

 

5972번: 택배 배송

접근한 방법

그래프의 간선 가중치를 고려한 최단 경로를 구하는 문제입니다. 힙 자료구조를 이용한 다익스트라 알고리즘으로 풀이할 수 있습니다.

 

dist는 노드 간의 최단 거리를 저장할 리스트로 초기값은 무한대(inf)로 초기화하고 1번 노드부터의 최단 거리를 나타냅니다. 

graph는 각 노드에 연결된 엣지 정보를 저장하는 리스트입니다.

 

먼저 그래프 정보를 구성해야 합니다. m번 반복하여 입력으로 주어지는 간선 정보를 바탕으로 생성합니다. 양방향 그래프이므로 두 노드 간의 연결 관계와 가중치를 저장합니다.

 

이후 우선순위 큐를 사용하여 다익스트라 알고리즘을 수행합니다. 초기에는 1번 노드부터 시작하므로 (0, 1)을 우선순위 큐에 추가합니다. hq(heap queue)는 최소 힙을 유지하는 자료구조로, 튜플 형태로 (거리, 노드)를 저장합니다.

우선순위 큐에서 노드를 하나씩 꺼내면서 해당 노드까지의 거리 vd와 노드 번호 v를 확인합니다. 현재 노드까지의 거리 vd가 이전에 저장된 최단 거리 dist[v]보다 작은 경우는 무시합니다.

현재 노드에서 이동 가능한 노드들을 확인하면서, 현재 거리 vd와 가중치 d를 더한 값이 해당 노드까지의 최단 거리 dist[t]보다 작으면 최단 거리를 업데이트하고, 우선순위 큐에 추가합니다.

 

모든 노드를 처리한 후 dist 리스트에는 각 노드까지의 최단 거리가 저장될 것입니다. 목표 지점 노드의 최단 거리를 출력하면 됩니다.

 

Python

import sys
input = sys.stdin.readline

inf = 1e9
n, m = map(int, input().split())
dist = [inf] * (n + 1)
dist[1] = 0
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))
from heapq import heappush, heappop
hq = []
heappush(hq, (0, 1))
while hq:
    vd, v = heappop(hq)
    if vd < dist[v]:
        continue
    for (t, d) in graph[v]:
        if vd + d < dist[t]:
            dist[t] = vd + d
            heappush(hq, (vd + d, t))
print(dist[-1])