백준 1753번 최단경로

문제 풀이

• 힙 자료구조를 이용해 다익스트라 알고리즘으로 문제를 해결할 수 있습니다.
• 우선순위가 높은(거리가 가장 짧은) 노드를 힙에서 뽑아내 최단거리를 갱신합니다.

코드 풀이

import sys, heapq
input = sys.stdin.readline

# V: 정점의 개수, E: 간선의 개수, K: 시작 정점
V, E = map(int, input().split())
K = int(input())

INF = int(1e9)
dist = [INF] * (V + 1)   # 각 노드 별 최단거리를 저장

graph = [[] for _ in range(V + 1)]
for _ in range(E):
	# u : 시작 노드, v : 도착 노드, w : 가중치
    u, v, w = map(int, input().split())
    graph[u].append([v, w])   # 다익스트라에서는 그래프에 가중치와 도착 노드를 함께 저장


def dijkstra(start):
    q = []
    dist[start] = 0
    heapq.heappush(q, [0, start])   # [최단거리, 노드]: 해당 노드까지 알려진 최단거리
    while q:
    	# 최단거리를 기준으로 우선순위가 높은 것을 먼저 뽑아냄.
        distance, now = heapq.heappop(q)
        # 현재까지 알려진 거리(dist[now])가 더 최단거리라면 해당 반복문을 스킵.
        if dist[now] < distance:
            continue
        # 아니라면 distance가 더 최단 경로라는 의미
        for i in graph[now]:
        	# 현재 노드(now)에서 다음 노드(i[1])까지의 거리(cost) 계산
            cost = distance + i[1]
            # cost가 현재까지 알려진 최단거리(dist[i[0]])보다 짧다면 최단거리를 cost로 갱신
            if cost < dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q, [cost, i[0]])


dijkstra(K)
for i in dist[1:]:
    if i == INF:
        print('INF')
    else:
        print(i)