[Python] 백준 1753번 - 최단경로

📖 문제

1753번: 최단경로

 

🔎 풀이

다익스트라를 활용하는 기본 문제입니다. 다익스트라 구현 시에는 우선순위 큐를 활용하여 가장 적은 비용을 우선적으로 뽑아내도록 해야합니다. 그리디하게 매순간 가장 적은 비용의 경로를 뽑아내고, 처음 방문하는 정점일 경우 따로 저장해줍니다.

 

💻 코드

import sys
import collections
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
graph = collections.defaultdict(list)
start = int(input())
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

q = [(0, start)]
# 각 정점까지의 거리를 저장
dist = collections.defaultdict(int)
while q:
    time, node = heapq.heappop(q)
    # 처음 방문하는 정점일 경우 방문
    if node not in dist:
        dist[node] = time
        for v, w in graph[node]:
            # 이전까지의 합과 현재 간선의 비용 합하기
            alt = time + w
            heapq.heappush(q, (alt, v))

for i in range(1, V+1):
    # 시작점인 경우
    if i == start:
        print(0)
    # 경로가 존재하는 경우
    elif dist[i]:
        print(dist[i])
    # 경로가 존재하지 않는 경우
    else:
        print("INF")