[백준 1916번] 최소비용 구하기 - 다익스트라(Dijkstra Algorithm)

1916번: 최소비용 구하기

import heapq
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())

INF = float("inf")

graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)

for _ in range(m):
    start, end, cost = map(int,input().split())
    graph[start].append((end,cost))

def dijkstra(start):
    
    distance[start] = 0
    
    q = []

    heapq.heappush(q,(0,start))

    while q:
        
        dist, current = heapq.heappop(q)

        if distance[current] < dist:
            continue

        for node,cost in graph[current]:
            new_cost = dist + cost

            if new_cost < distance[node]:
                distance[node] = new_cost
                heapq.heappush(q,(new_cost,node))

target_start, target_dest = map(int,input().split())

dijkstra(target_start)

print(distance[target_dest])

이번 문제는 전형적인 다익스트라 문제로, '특정 노드에서 특정 노드까지 도달할 수 있는 최단 거리'를 구하는 문제이다.

 

여기서 조심해야할 것은 그래프에 경로를 저장할 때는 (도착 지점, 거리) 순으로 저장해야 하지만, heapq 에 넣을 때는 반드시 (거리, 노드)순으로 넣어야 한다는 점이다. ⭐️

 

시간복잡도 O(V^2)를 가진 다익스트라 알고리즘이 아니라, O(ElogV) 시간복잡도를 가진 다익스트라 알고리즘으로 풀이하고, input 대신 sys.stdin.readline 을 사용하니 시간초과 없이 통과할 수 있었다 :)