[파이썬, Python] 백준 1753: 최단경로

문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

코드

import sys
import heapq
input = sys.stdin.readline

INF = int(1e9)

V, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V + 1)]

for _ in range(e):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dis = [INF] * (V + 1)

def dijkstra(start):
    q = []
    dis[start] = 0
    heapq.heappush(q, (0, start))

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

        if dis[node] < dist:
            continue

        for i in graph[node]:
            cost = dist + i[1]

            if cost < dis[i[0]]:
                dis[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, V + 1):
    if dis[i] == INF:
        print("INF")
    else:
        print(dis[i])

설명

다익스트라를 통해 해결이 가능한 문제다.

우선 입력값을 다 받아준다.
양방향 간선이 아니기 때문에 간선을 받을 때 유의해준다.

그리고 거리를 받을 dis를 만들어준다.

일반적인 다익스트라 알고리즘으로 해결이 가능하다.

우선 큐로 사용할 리스트를 하나 생성해 준다.
그리고 시작점의 거리를 0으로 지정해 준다.
그리고 heapq를 이용하여 우선순위 큐에 거리인 0과 시작점의 노드를 넣어준다.

이후 큐가 존재하는 동안 heappop 하여 각 거리와 노드를 받아준다.
이때 거리가 현재 거리보다 크다면 건너뛰고 그렇지 않다면 다음 단계를 진행한다.

해당 노드와 연결되어 있는 간선의 최단 거리를 갱신하는 작업을 진행한다.
현재까지의 거리에 다음 노드로 이어지는 거리를 더한 값을 계산해 주고
해당 값이 현재 최단거리보다 짧다면 거리를 갱신하고 해당 값과 노드를 큐에 넣어준다.

이렇게 큐가 없어질 때까지 반복하여 거리를 구한다.

출력 형식에 맞춰 만약 INF 라면 해당 노드에 도달하지 못한다는 뜻이므로 INF를 출력하고
그렇지 않다면 거리를 출력해 준다.