BOJ 1753 PS일기 - dijkstra

요구사항

O(ElgE)의 시간복잡도로 모든 정점까지 그래프 최단경로를 찾아야한다.

V : 정점(노드)의 갯수

E : 간선의 갯수

문제접근

힙을 이용한 최소비용의 경로를 우선순위로 연산하여 노드가 2만개까지 대량으로 주어줘도 빠르게 찾을 수 있도록 목표를 잡았다.

데이터 흐름

bfs알고리즘과 기본흐름이 유사하다. 각 노드의 최소비용 리스트를 무한(매우 큰 수)로 초기화하고 힙에 들어가는 원소들은 노드의 비용과 번호를 넣도록한다. while 반복문 안에서는 현재 처리중인 노드와 연결된 노드에 대해 (현재 노드 비용 + 그 노드 비용)이 먼저 선언한 최소비용 리스트의 그 노드의 비용보다 작다면 갱신하고 힙에 새롭게 갱신된 그 노드의 비용, 그 노드의 번호 순으로 넣어주고 반복한다. 최소비용 리스트가 완성되었다면 문제에서 요구한 양식대로 출력하도록한다.

import heapq,sys

v,e = [*map(int, sys.stdin.readline().split(' '))]
start = int(sys.stdin.readline())
info = dict()
for i in range(e):
    point1, point2, cost = [*map(int, sys.stdin.readline().split(' '))]
    if point1 in info:
        info[point1] += [(point2,cost)]
    else:
        info[point1] = [(point2,cost)]

hq = [(0,start)]
inf = 2**99
d = [inf for _ in range(20001)]
d[start] = 0

while hq:
    cost,curr = heapq.heappop(hq)
    if d[curr] != cost:
        continue
    if curr not in info:
        continue
    for nxt,nxtCost in info[curr]:
        if d[curr] + nxtCost >= d[nxt]:
            continue
        d[nxt] = d[curr] + nxtCost
        heapq.heappush(hq, (d[nxt], nxt))
        
for i in range(1, v + 1):
    print(d[i] if d[i] != inf else 'INF')