[파이썬/python] 백준 - 5972 택배 배송

문제

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

---

문제 설명

1. $N$개의 헛간과, 소들의 길인 $M$개의 양방향 길이 그려져 있다.
   1. 각각의 길은 $C_i$마리의 소가 있다.
   2. 소들의 길은 두 개의 떨어진 헛간인 $A_i$와 $B_i$를 잇는다.
   3. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있다.
2. 농부 현서는 헛간 1에 있고 찬홍이는 헛간 N에 있다.
3. 현서가 찬홍이에게 택배를 배송해주면서 지나가는 길에는 소들에게 여물을 줘야한다.
4. 여물을 최소로 주면서 이동했을 때 최소 여물을 구한다.

 

---

풀이

정말 전형적인 다익스트라 문제이다.

 

다익스트라의 기본 구현은 항상 비슷하다.

 

1. 문제에서 주어진 노드 간 cost를 graph를 통해 초기화한다.
2. dist 배열을 통해 현재 노드까지의 총 cost를 갱신한다. (초기값은 최댓값으로 갱신하고 시작점은 0으로 시작한다.)
3. hq에 시작점을 넣고 탐색을 시작한다.
4. 노드 하나를 꺼낸다.
   1. 만약 현재 꺼낸 노드의 cost가 해당 노드의 최솟값인 dist [v1]의 값보다 크다면 다음 노드를 꺼낸다.
5. v1에서 갈 수 있는 v2를 모두 탐색하며 cost가 적어지는 경로를 갱신한다.
6. N위치의 최솟값을 출력한다.

 

골드 5 기준의 다익스트라 문제는 위의 틀을 벗어나지 않는다. BFS, DFS, 이분탐색처럼 기본 틀을 가지고 있는 알고리즘은 물론 이해도 해야 하지만 양으로 승부 보는 것이 좋다고 생각한다. 많이 풀다 보면 자연스럽게 코드가 외워지는(?) 지경까지 올 수 있다.

 

이런 문제들을 풀다보면 백준은 티어가 전부가 아니라는 것을 새삼 느낀다..

---

코드

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

N,M = map(int,input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    v1,v2,c = map(int,input().split())
    graph[v1].append((v2,c))
    graph[v2].append((v1,c))

dist = [INF for _ in range(N+1)]
dist[1] = 0

hq = []
heapq.heappush(hq, (0,1))

while hq:
    cur_cost, v1 = heapq.heappop(hq)

    if dist[v1] < cur_cost:
        continue
    
    for v2,cost in graph[v1]:

        if cur_cost + cost < dist[v2]:
            dist[v2] = cur_cost + cost
            heapq.heappush(hq,(dist[v2], v2))

print(dist[N])

---

시간복잡도

• 다익스트라의 시간복잡도는 $O(ElogV)$
• 최악의 경우 $V = 50000, E = 50000$이므로 시간복잡도는 약 $O(50000*15) = O(10^6)$이다.