💻 1753: 최단경로

문제 소개 🧐

주어진 방향 그래프에서 특정 시작 정점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제이다. 간선의 가중치는 양수이며, 음의 가중치는 존재하지 않는다.

입력 📝

  • 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
  • 모든 정점은 1부터 V까지 번호가 매겨져 있다.
  • 둘째 줄에는 시작 정점의 번호 K가 주어진다.
  • 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 u, v, w가 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. 간선의 가중치 w는 10 이하의 자연수이며, 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있다.

출력 📤

K번째 줄부터 V개의 줄에 걸쳐, K에서 i번째 정점으로의 최단 경로의 가중치를 출력한다. 경로가 존재하지 않으면 “INF”를 출력한다.

제한 ❌

  • 시간: 2초
  • 메모리: 256MB

나의 풀이: 다익스트라 알고리즘 🎉

Idea

단일 시작점에서 모든 다른 정점으로의 최단 경로를 찾는 문제이다. 따라서 다익스트라(Dijkstra) 알고리즘을 사용하여 해결할 수 있겠다고 생각했다.

첫 번째 시도 (메모리 초과):
처음에는 그래프를 인접 행렬(graph = [[float('inf') for _ in range(V)] for _ in range(V)])로 표현하여 풀이를 시도했다. 하지만 V의 최대값이 20,000이므로, 20000 * 20000 크기의 행렬은 약 3.2GB의 메모리를 필요로 하여 메모리 제한(256MB)을 초과하게 되었다.

Idea 2

두 번째 시도:

  • 메모리 초과 문제를 해결하기 위해 그래프 표현 방식을 인접 리스트(adjacency list)로 변경했다. 파이썬의 딕셔너리(graph = {})를 사용하여 각 노드에 연결된 간선 정보만을 저장함으로써 메모리 사용량을 크게 줄일 수 있었다.
  • 또한, visited_node 배열을 따로 관리하지 않고, path 배열(최단 거리를 저장하는 배열)의 값을 통해 이미 처리된 노드인지 확인한다. 우선순위 큐(heapq)를 사용하여 최단 거리가 짧은 노드부터 탐색하는 방식으로 효율성을 유지했다.

Code

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline().rstrip()) - 1

graph = {}

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    if not graph.get(u-1):
        graph[u-1] = [(w, v-1)]
    else:
        graph[u-1].append((w, v-1))

def get_shortest_path(start_node):
    global graph
    global V
    q = []
    q.append((0, start_node))
    path = [float('inf') for _ in range(V)]
    path[start_node] = 0
    
    while q:
        w, cur_v = heapq.heappop(q)

        if w > path[cur_v]: # 이미 더 짧은 경로를 찾은 경우 스킵
            continue

        if not graph.get(cur_v):
            continue

        for n_w, next_node in graph[cur_v]:
            if path[next_node] > w + n_w:
                path[next_node] = w + n_w
                heapq.heappush(q, (w + n_w, next_node))
    
    return path

short_path = get_shortest_path(k)

for i in range(V):
    print(str(short_path[i]).upper())

Result

성공! ✅

배운 점 및 느낀 점 ✍️

  • 그래프 표현의 중요성: 문제의 제약 조건(V의 크기)을 고려하여 적절한 그래프 표현 방식(인접 행렬 vs. 인접 리스트)을 선택하는 것이 매우 중요하다는 것을 깨달았다.
  • 다익스트라 알고리즘의 핵심: 음의 가중치가 없는 그래프에서 단일 시작점으로부터 모든 노드까지의 최단 경로를 찾는 데 최적화된 알고리즘이다.
  • 우선순위 큐의 활용: heapq 모듈을 사용하여 우선순위 큐를 구현함으로써, 항상 현재까지 발견된 최단 거리가 가장 짧은 노드를 먼저 처리할 수 있었다
  • “INF” 처리: 도달할 수 없는 노드에 대한 예외 처리를 float('inf')를 사용하여 깔끔하게 처리하고, 최종 출력 시 “INF” 문자열로 변환하는 방법을 적용했다.