[BOJ] 최소비용 구하기

---

코드

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
dist = [10e9]*(n+1)    # 도시 n까지 가는 최소비용

ans = sys.maxsize

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

def dijkstra(start):
    # 최소 힙을 사용한 다익스트라
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        d, now = heapq.heappop(q)    # 최단거리가 가장 짧은 노드
        if dist[now] < d:    # 이미 방문한 경우 무시
            continue
        for adj in graph[now]:
            cost = d + adj[1]    # 현재 노드를 거쳐서 인접 노드까지 가는 비용
            if cost < dist[adj[0]]:    # 비용이 더 작은 경우 갱신
                dist[adj[0]] = cost
                heapq.heappush(q, (cost, adj[0]))    # 인접노드를 최소힙에 추가

st, e = map(int, input().split())
dijkstra(st)
print(dist[e])

결과

풀이 방법

• 다익스트라 알고리즘을 사용하는 문제이다
• 다익스트라 알고리즘은 노드 간 음의 비용이 존재하지 않을 때 시작 노드(start)로부터 각 노드까지의 최소 비용을 구하는 데 유용하다
• 노드를 방문할 때마다 최소비용을 갖는 인접 노드를 선택해야 하는데 이때 최소힙을 사용하면 O(1)의 시간복잡도로 선택할 수 있다.
• 인접 노드를 방문하고 heappush 연산을 할 때마다 O(logN)의 시간이 소요된다
• 따라서 최대 N개 노드를 방문하므로 다익스트라 알고리즘의 시간복잡도는 O(NlogN)이다

---