[Python] 백준 1753번 - 최단경로(다익스트라 알고리즘) 문제풀이

문제링크

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

1753번: 최단경로

알고리즘

시작점이 주어지고 다른 노드까지의 최단거리를 주는 문제는 다익스트라 알고리즘의 정석이라고 할 수 있다.

간선의 가중치가 모두 양수이기 때문에 다익스트라 알고리즘을 사용할 수 있고,

만약 가중치에 음수가 포함된다면 밸만포드(Bellman-Ford) 알고리즘을 사용해야할 것이다.

 

다익스트라 알고리즘도 우선순위 큐를 사용하면 시간복잡도를 O(NlogN)으로 줄일 수 있다.

코드

from collections import defaultdict
import sys
import heapq  # 우선순위 큐


def dijkstra(graph, start):
    distances = [1e9] * (n + 1)
    distances[start] = 0  # 시작 노드와의 거리는 0
    q = []
    heapq.heappush(q, [distances[start], start])  # 시작노드부터 탐색

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

        if dist > distances[node]:  # 기존 최단거리보다 멀다면 무시
            continue

        for n_node, n_dist in graph[node]:  # 인접 노드 탐색
            distance = dist + n_dist  # 인접 노드와의 거리
            if distance < distances[n_node]:  # 기존 거리보다 짧으면 갱신
                distances[n_node] = distance
                heapq.heappush(q, [distance, n_node])  # 다음 인접노드 탐색
    return distances


if __name__ == "__main__":
    input = sys.stdin.readline

    n, m = map(int, input().split())
    start = int(input())
    graph = defaultdict(list)

    for i in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))  # (도착지, 가중치)

    dist_lst = dijkstra(graph, start)
    for i in range(1, n + 1):
        if dist_lst[i] == 1e9:
            print("INF")
            continue
        print(dist_lst[i])

제출결과