[알고리즘/개념] 다익스트라(Dijkstra) 완벽 해부 - 외우지 않고 뼈대 세우기

학습 철학 회고
특정 문제의 꼬인 조건에 맞춰진 코드를 달달 외우는 것은 융통성을 잃게 만듭니다. 알고리즘의 본질을 '언어'로 먼저 이해하고, 그것을 순수한 템플릿으로 추상화한 뒤, 실전 문제의 요구사항에 맞춰 조립하는 '설계 주도형 사고(SOP)'를 다익스트라 알고리즘에 적용해 보았습니다.

📌 개념 요약: 다익스트라는 무엇인가?

"하나의 시작점에서 다른 모든 도착점까지 가는 '최단 경로(최소 비용)'를 찾는 길찾기 내비게이션"입니다. 단, 과거로 돌아가는 길(음수 가중치)은 존재하지 않는다는 강력한 전제가 있습니다.

💡 동작 원리 (핵심 로직)

다익스트라는 소문을 퍼뜨리고 메모장을 수정하는 과정과 같습니다.

1. 가장 싼 곳 먼저 방문 (Greedy): 현재까지 알려진 경로 중 가장 비용이 적게 드는 노드를 우선 방문합니다.
2. 지름길 갱신 (Memoization): 그 노드를 거쳐서 이웃 노드로 가는 비용을 계산합니다. 만약 내가 기존에 알던 길보다 방금 방문한 노드를 거쳐 가는 것이 더 싸다면, 최단 거리 메모장을 갱신합니다.
3. 자료구조의 선택 (Min-Heap): 1번 과정에서 '가장 싼 곳'을 찾기 위해 매번 전체 배열을 뒤지면 $O(V^2)$의 시간이 걸립니다. 이를 해결하기 위해 파이썬의 heapq(우선순위 큐)를 사용하여 탐색 시간을 $O(E \log V)$로 혁신적으로 단축합니다.

🧠 핵심 증명: 큐에서 특정 노드를 처음으로 pop한 순간 왜 '최단 거리'로 확정되는가?

단순히 코드를 암기하는 것을 넘어, 다익스트라 알고리즘의 무결성을 귀류법(Proof by Contradiction)으로 증명합니다. (전제 조건: 모든 간선의 가중치 $w \ge 0$)

1. 가설 설정: 우선순위 큐에서 가장 비용이 작은 노드 $u$가 팝(Pop)되었고, 이때의 기록된 비용을 $d(u)$라고 합시다. 만약 $d(u)$가 진짜 최단 거리가 아니며, 아직 발견하지 못한 더 짧은 진짜 최단 경로 $D(u)$가 존재한다고 가정해 봅니다. 즉, $D(u) < d(u)$ 입니다.
2. 진짜 최단 경로 추적: 출발지 $S$에서 $u$로 가는 진짜 최단 경로를 따라가다 보면, 이미 방문이 확정된 노드 그룹을 벗어나 가장 처음 마주치는 '미확정 노드' $x$가 반드시 존재합니다.
3. 비용의 대소 관계: 출발지에서 이 중간 기착지 $x$까지 도달하는 비용을 $d(x)$라고 합시다. 그래프의 모든 가중치는 0 이상이므로, $x$를 거쳐 종착지 $u$로 가는 동안 거리는 무조건 늘어나거나 최소한 유지됩니다. 따라서 $d(x) \le D(u)$ 가 성립합니다.
4. 모순 발생: 위 수식들을 연결하면 $d(x) \le D(u) < d(u)$ 가 되며, 결론적으로 $d(x) < d(u)$ 가 도출됩니다.
5. 결론: 우선순위 큐는 '가장 값이 작은 노드'를 먼저 꺼내는 자료구조입니다. 만약 $d(x) < d(u)$ 가 사실이라면, 큐에서는 $u$가 아니라 $x$가 먼저 팝(Pop)되었어야 합니다. 이는 "노드 $u$가 큐에서 가장 먼저 꺼내졌다"는 현재의 팩트와 정면으로 충돌하므로 모순입니다. 따라서 초기 가설은 거짓이 되며, "큐에서 꺼내진 노드 $u$의 비용 $d(u)$보다 더 짧은 경로는 존재할 수 없다"는 것이 수학적으로 증명됩니다.

💻 추상화된 템플릿 코드

어떤 문제의 엣지 케이스(Edge Case)에도 오염되지 않은, 가장 범용적인 순수 파이썬 다익스트라 뼈대입니다.

import heapq

def dijkstra_template(start, graph, n):
    INF = int(1e9) # 무한대
    distance = [INF] * (n + 1) # 메모장 초기화
    
    pq = []
    # 힙은 첫 번째 원소 기준으로 정렬되므로 반드시 (비용, 노드) 순으로 삽입
    heapq.heappush(pq, (0, start)) 
    distance[start] = 0
    
    while pq:
        current_cost, current_node = heapq.heappop(pq)
        
        # [방어 로직] 이미 처리된 적이 있는 노드라면 무시 (지연 삭제)
        if distance[current_node] < current_cost:
            continue
            
        for weight, next_node in graph[current_node]:
            cost = current_cost + weight # 거쳐서 가는 총 비용
            
            # [핵심] 거쳐가는 것이 기존 경로보다 싸다면 (지름길 발견)
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(pq, (cost, next_node))

    return distance

🚨 설계 및 회고

• 생명주기 관리: distance 배열과 pq를 전역 변수로 두지 않고 함수 내부에 가두어, 여러 번의 테스트 케이스가 주어져도 이전 데이터가 섞이는 치명적인 사이드 이펙트(Side Effect)를 원천 차단했습니다.
• 튜플 정렬의 원리: 파이썬 heapq의 특성을 살려 (비용, 도착점) 순서로 튜플을 구성함으로써, 별도의 정렬 함수 구현 없이 자연스럽게 최소 비용 노드가 추출되도록 설계했습니다.
• BFS와의 비교: 결국 다익스트라 알고리즘은 BFS의 업그레이드 버전입니다. 시작 노드에서 다음 노드들을 전부 큐에 넣고, 다 넣으면 그 노드의 인접한 노드들을 또 큐에 넣는 완벽한 BFS 형식입니다. 하지만 여기서 heapq를 사용함으로써, 맹목적인 탐색이 아닌 비용이 최소인 인접 노드를 먼저 탐색하도록 통제하는 점이 가장 중요한 차이점입니다.

🤔 심화 고찰: 왜 힙에 중복 데이터 푸시를 사전에 차단하지 않을까? (Lazy Deletion)

다익스트라 알고리즘을 설계하다 보면 아주 자연스럽게 다음과 같은 엔지니어링적 의문이 듭니다.
"불필요한 낡은 데이터가 힙(Heap)에 들어가는 것 자체를 사전에 차단하면 큐가 가벼워져서 시간 복잡도를 더 줄일 수 있지 않을까?"

이 의문은 자료구조 최적화의 핵심 쟁점이며, 작성된 템플릿 코드에는 이 딜레마를 해결하기 위한 의도적인 트레이드오프(Trade-off)가 숨어있습니다.

1. 이미 최단 거리가 확정된 노드는 애초에 푸시되지 않는다
"이미 팝(Pop)되어 최단 거리가 고정된 노드는 더 이상 힙에 넣지 말자"는 완벽한 논리는 아래의 단 한 줄의 코드가 이미 수행하고 있습니다.

if cost < distance[next_node]:

어떤 노드가 이미 큐에서 꺼내져(Pop) 최단 거리가 영구 확정되었다면, 그 노드의 distance 메모장 값은 수학적으로 도달 가능한 '절대적 최솟값' 상태입니다. 따라서 나중에 탐색을 돌다가 다른 길을 통해 이 노드로 다시 진입하려 해도, 그 새로운 비용(cost)은 무조건 기존 최솟값보다 크거나 같을 수밖에 없습니다. 결과적으로 조건문이 False가 되어 이미 확정된 노드는 힙에 두 번 다시 푸시되지 않습니다.

2. 자료구조의 물리적 한계와 '지연 삭제(Lazy Deletion)' 전략
그렇다면 힙에 중복된 낡은 데이터가 쌓이는 진짜 이유는 무엇일까요? 바로 '아직 팝되지 않고 힙에서 대기 중인 노드'에 대해 더 짧은 지름길을 발견했을 때 발생합니다.

이때 중복 푸시를 막으려면, 힙 내부를 뒤져서 대기 중이던 낡은 경로 값을 찾아 지우거나 새 값으로 갱신(Decrease-key)해야 합니다.

• 힙 탐색의 비용: 일반적인 우선순위 큐(이진 힙)는 최솟값을 뽑는 데는 최적화되어 있지만, 내부의 특정 원소를 찾는 데는 최악의 경우 $O(V)$ (V는 노드 수)의 시간이 걸립니다.
• 새로운 값 푸시 비용: 반면, 낡은 값을 그대로 둔 채 새로운 값을 힙의 말단에 밀어 넣는 데는 고작 $O(\log V)$의 시간밖에 걸리지 않습니다.

즉, 중복을 막겠다고 매번 $O(V)$의 막대한 비용을 지불하며 힙을 뒤지는 것보다, 그냥 $O(\log V)$로 중복 데이터를 밀어 넣는 것이 전체 시스템 관점에서는 압도적으로 효율적입니다. 어차피 힙의 특성상 값이 더 작은 '진짜 최단 경로'가 먼저 팝되어 메모장을 갱신할 것입니다.

이후 힙 구석에 방치되어 있던 '낡은 데이터'가 뒤늦게 팝되어 나오면, 우리는 이미 준비해 둔 방어 로직(if distance[current_node] < current_cost: continue)을 통해 단 $O(1)$의 비용으로 무시하고 폐기(Discard)해 버리면 됩니다. 이것이 바로 컴퓨터 과학에서 널리 쓰이는 지연 삭제(Lazy Deletion) 아키텍처입니다.