백준 1753 최단경로: Python heapq 다익스트라 풀이

백준 1753번 ‘최단경로’는 방향 그래프에서 시작 정점부터 모든 정점까지의 최단 거리를 구하는 문제다. 간선 가중치가 양수이므로 heapq를 이용한 다익스트라 알고리즘을 적용할 수 있다.

이 문제에서 중요한 구현 포인트는 세 가지다.

• 인접 행렬이 아니라 인접 리스트로 최대 300,000개의 간선을 저장한다.

• heap에는 (현재까지 거리, 정점) 순서로 넣어 가장 가까운 정점을 먼저 꺼낸다.

• 같은 정점의 예전 거리도 heap에 남을 수 있으므로 stale entry를 건너뛴다.

• 백준 1753번 문제

문제를 그래프로 바꾸기

입력은 u v w 형태의 방향 간선을 준다. 이는 정점 u에서 v로 이동하는 비용이 w라는 뜻이다. 반대 방향 간선은 별도로 주어졌을 때만 존재한다.

시작 정점의 거리는 0, 나머지 정점의 거리는 아직 갈 수 없다는 뜻으로 무한대에서 시작한다. 어떤 정점까지의 더 짧은 경로를 찾으면 거리를 갱신하고 heap에 새 후보를 넣는다. 모든 탐색이 끝난 뒤에도 무한대인 정점은 시작점에서 도달할 수 없으므로 INF를 출력한다.

다익스트라가 동작하는 이유

heap에서 아직 처리할 후보 중 거리가 가장 작은 (distance, node)를 꺼낸다. 모든 간선 가중치가 음수가 아니므로 이 거리보다 더 짧은 경로가 나중에 갑자기 만들어질 수 없다. 해당 정점에서 나가는 간선을 따라가며 다음 식으로 완화(relaxation)한다.

새 거리 = 현재 정점까지의 거리 + 간선 가중치

새 거리가 기존 기록보다 작을 때만 갱신한다. Python heapq에는 임의 원소의 우선순위를 직접 낮추는 decrease-key 연산이 없다. 대신 새 거리로 다시 push하고, 나중에 예전 항목을 꺼냈을 때 현재 최단 거리와 다르면 버린다.

Python 코드

import heapq
import sys


def dijkstra(graph, start):
    distances = [float("inf")] * len(graph)
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance != distances[current_node]:
            continue

        for next_node, weight in graph[current_node]:
            next_distance = current_distance + weight

            if next_distance < distances[next_node]:
                distances[next_node] = next_distance
                heapq.heappush(queue, (next_distance, next_node))

    return distances


read = sys.stdin.buffer.readline
vertex_count, edge_count = map(int, read().split())
start_vertex = int(read())

graph = [[] for _ in range(vertex_count + 1)]

for _ in range(edge_count):
    source, destination, weight = map(int, read().split())
    graph[source].append((destination, weight))

result = dijkstra(graph, start_vertex)

output = []
for vertex in range(1, vertex_count + 1):
    if result[vertex] == float("inf"):
        output.append("INF")
    else:
        output.append(str(result[vertex]))

sys.stdout.write("\n".join(output))

graph와 distances를 정점 번호와 바로 맞추기 위해 길이를 V + 1로 만들었다. 입력을 먼저 edges list에 모두 모았다가 graph로 옮기지 않고 읽는 즉시 인접 리스트에 넣어 중복 메모리도 피했다.

대량 입력에서는 sys.stdin.buffer.readline을 사용했다. input()과의 동작 차이는 Python input()과 readline() 비교에서 따로 정리했다.

예제 실행

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

시작 정점 1에서 2까지는 비용 2, 3까지는 비용 3이다. 4까지는 1 → 2 → 4의 비용 7이 가장 짧다. 5로 가는 방향 간선은 없으므로 도달할 수 없다.

0
2
3
7
INF

시간 복잡도와 공간 복잡도

인접 리스트를 만드는 데 O(V + E) 공간을 사용한다. 한 번의 성공적인 완화마다 heap에 후보가 들어갈 수 있으므로 heap에는 중복 정점이 생기며 최악에는 O(E)개의 entry가 쌓일 수 있다.

binary heap의 push와 pop이 O(log E)이므로 이 구현의 시간 복잡도는 O((V + E) log E), 전체 공간 복잡도는 O(V + E)로 볼 수 있다. heap 크기가 항상 정점 수 V 이하라고 설명하면 중복 entry를 빠뜨린 셈이다.

자주 틀리는 지점

양방향 간선으로 넣지 않기

이 문제의 간선은 방향이 있다. graph[v].append((u, w))까지 자동으로 추가하면 다른 graph가 된다.

방문 배열만 믿지 않기

정점을 heap에 넣었다고 최단 거리가 확정된 것은 아니다. 더 짧은 후보가 나중에 들어갈 수 있다. 이 코드는 별도 방문 배열 대신 current_distance != distances[current_node]로 오래된 후보를 거른다.

도달 불가능한 정점 처리하기

거리 배열의 무한대가 그대로 출력되면 안 된다. 문제 요구에 맞춰 문자열 INF로 바꾼다.

다익스트라를 다른 문제에 적용한 예시는 백준 1916 최소비용 구하기에서 이어서 볼 수 있다.

검증 메모

이 글의 문제 조건과 예시는 기존 글에 남아 있던 내용을 기준으로 코드 실행까지 확인했다. 2026년 8월 2일 현재 백준 문제 URL은 문제 본문 대신 서비스 준비 안내를 표시해, 현행 채점기에 다시 제출하는 검증은 할 수 없었다.

참고 자료

• Python heapq
• 백준 1753번 문제