[백준] 5972: 택배 배송 python 구현 / 다익스트라, 시간복잡도

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

 

풀이

최소 경로 찾기 문제 

처음에 DFS로 풀었다가 시간초과나서 다익스트라 알고리즘으로 풀었다. 그런데 for문을 쓰는 다익스트라는 시간초과가 나고, 우선순위 큐를 쓰는 알고리즘은 통과하더라 ! 여기서 시간 복잡도에 대한 정리가 필요할 것 같다.

 

코딩 테스트 문제를 처음 만났을 때 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)이다.

시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같다.

• $0 \le N < 500$ : $O(N^3)$
• $0 \le N < 2,000$ : $O(N^2)$
• $0 \le N < 100,000$ : $O(NlogN)$
• $0 \le N < 10,000,000$ : $O(N)$

여기서 해당 문제의 시간 제한은 1초이다.

그리고 N의 범위가 50,000이니까 적어도 $O(NlogN)$의 시간 복잡도를 가진 알고리즘을 사용해서 풀어야 하는 것이다 ! 

 

따라서 quadratic for문을 쓰는 다익스트라가 아닌 $O(NlogN)$의 시간 복잡도를 가진 우선순위 큐를 사용한 다익스트라를 활용해야 한다. 

 

CODE

import sys
import heapq

n, m = map(int, input().split())
graph = {i: [] for i in range(1, n+1)}
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

distance = [float('inf')]*(n+1)

def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start)) # cost, node
    while heap:
        dist, now = heapq.heappop(heap) # 가장 거리가 가까운 node를 pop
        # pop한 거리가 최소 거리(distance)보다 클 경우는 무시 (= 이미 방문 했음)
        if distance[now] < dist:
            continue
        
        # 그게 아닐 경우 인접 노드들을 탐색
        for i in graph[now]:
            cost = dist + i[1] # now까지의 거리 + 인접 노드까지 거리
            if cost < distance[i[0]]: # distance의 값보다 작으면 갱신
                distance[i[0]] = cost
                heapq.heappush(heap, (cost, i[0]))  # 다음 값을 queue에 push

start = 1
dijkstra(start)

print(distance[n])