다중 출처 다익스트라 (Multi-Source Dijkstra)

그래프 탐색 문제를 풀다 보면 "여러 개의 출발점 중 어느 곳에서 출발하든 상관없이 가장 가까운 목적지까지의 최단 거리를 구하라"는 조건을 만날 때가 있습니다.

이때 출발점마다 다익스트라 알고리즘을 매번 실행하면 반드시 시간 초과가 발생합니다. 이를 해결하는 핵심 기법이 바로 다중 출처 다익스트라(Multi-Source Dijkstra)입니다.

---

1. 일반 다익스트라 vs 다중 출처 다익스트라

구분	일반 다익스트라 (Single-Source)	다중 출처 다익스트라 (Multi-Source)
출발점	단 1개의 시작 노드	여러 개의 시작 노드 그룹
탐색 목적	특정 출발점에서 다른 노드들까지의 최단 거리	가장 가까운 출발점 기준으로 다른 노드까지의 최단 거리
PQ 초기화	시작 노드 1개만 dist = 0 설정 후 PQ 삽입	모든 시작 노드를 dist = 0 설정 후 PQ에 한 번에 삽입
시간 복잡도	O((V + E) log V) (출/도착 노드 반복 필요)	O((V + E) log V) (다중 출발이라도 1회만 호출)

핵심 아이디어

다중 출처 다익스트라의 원리는 간단합니다. "모든 출발점의 거리를 0으로 만들고 동시에 출발선에 세운 뒤 탐색을 시작하는 것"입니다.

우선순위 큐(PQ)는 알아서 가장 거리가 가까운 경로부터 꺼내어 처리하므로, 어떤 노드에 먼저 도달한 출발점이 있다면 그 출발점이 해당 노드까지의 가장 가까운 출처가 됩니다.

---

2. 알고리즘 수도코드 (Pseudo-code)

1. dist 배열 초기화
   - dist[노드ID] = INFINITY

2. 우선순위 큐(PQ) 생성
   - 정렬 기준: 비용(거리, 소모량 등등)이 가장 작은 노드가 먼저 poll 되도록 설정

3. 모든 출발 노드(start) 초기화 및 PQ 삽입
   - FOR EACH start IN gates:
       dist[start] = 0
       PQ.offer(비용 0, start 노드 ID)

4. WHILE (PQ가 비어있지 않을 때까지):
   a. pollNode = PQ.poll()
   b. pVal = pollNode의 비용, pIdx = pollNode의 노드 ID

   c. [가지치기 / Pruning]
      IF dist[pIdx] < pVal :
          CONTINUE (이미 더 짧은 경로로 방문된 적이 있으므로 스킵)

   d. [목적지 및 조건 처리]
      IF pIdx가 목적지(산봉우리/End)인 경우 :
          CONTINUE (목적지 너머로 확장을 막음)

   e. [다음 노드 탐색 (Relaxation)]
      FOR EACH nextNode IN graph[pIdx] :
          - nextIdx = nextNode.to
          - nextVal = 새로 계산한 비용 (누적 합: pVal + weight / 병목 최댓값: Math.max(pVal, weight))

          IF dist[nextIdx] > nextVal :
              dist[nextIdx] = nextVal
              PQ.offer(nextVal, nextIdx)

---

3. 자바(Java) 구현 코드 예시

프로그래머스 '등산코스 정하기' 문제를 기준으로 구현한 다중 출처 다익스트라 코드입니다.

• List<List<Node>> 구조를 사용하여 자바 제네릭 경고 없이 안전하게 인접 리스트를 구성했습니다.
• gates 배열 전체를 초기 PQ에 넣고 단 1번만 다익스트라를 수행합니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {

    static class Node {
        int to, weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    int n;
    List<List<Node>> graph;
    final int INFINITY = 20_000_000;
    boolean[] isSummit;

    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        this.n = n;

        // 1. 인접 리스트 초기화 (List<List<Node>>)
        this.graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 2. 산봉우리 체크 배열 생성 및 정렬
        Arrays.sort(summits);
        isSummit = new boolean[n + 1];
        for (int summit : summits) {
            isSummit[summit] = true;
        }

        // 3. 그래프 간선 연결
        for (int[] path : paths) {
            graph.get(path[0]).add(new Node(path[1], path[2]));
            graph.get(path[1]).add(new Node(path[0], path[2]));
        }

        // 4. 단 1번의 다중 출처 다익스트라 실행
        int[] dist = dijkstra(gates);

        // 5. 결과 도출 (최소 intensity를 갖는 번호가 가장 작은 산봉우리)
        int answerSummit = 0;
        int answerWeight = INFINITY;

        for (int summit : summits) {
            if (dist[summit] < answerWeight) {
                answerSummit = summit;
                answerWeight = dist[summit];
            }
        }

        return new int[] { answerSummit, answerWeight };
    }

    int[] dijkstra(int[] gates) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INFINITY);

        // PQ 정렬 기준: {intensity, node} 중 intensity(index 0) 오름차순
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

        // [Multi-Source] 모든 출입구(gates)를 시작점으로 PQ에 동시에 넣음
        for (int gate : gates) {
            dist[gate] = 0;
            pq.offer(new int[] { 0, gate });
        }

        while (!pq.isEmpty()) {
            int[] pollNode = pq.poll();
            int pVal = pollNode[0]; // 현재까지의 intensity
            int pIdx = pollNode[1]; // 노드 번호

            // 가지치기: 이미 처리된 거리가 더 짧다면 스킵
            if (dist[pIdx] < pVal) {
                continue;
            }

            // 산봉우리에 도착하면 다른 길로 더 이상 탐색하지 않음
            if (isSummit[pIdx]) {
                continue;
            }

            // 인접 노드 순회
            for (Node nextNode : graph.get(pIdx)) {
                int nextIdx = nextNode.to;
                int nextVal = Math.max(pVal, nextNode.weight); // 병목 구간 계산

                // 최단 거리(최소 intensity) 갱신 및 PQ 삽입
                if (dist[nextIdx] > nextVal) {
                    dist[nextIdx] = nextVal;
                    pq.offer(new int[] { nextVal, nextIdx });
                }
            }
        }

        return dist;
    }
}

---

4. 왜 다중 출처 다익스트라를 써야 하는가?

만약 출입구(gates)가 25,000개, 산봉우리(summits)가 25,000개라고 가정해 봅시다.

1. 잘못된 접근 (반복 다익스트라)

• 출입구 $\times$ 산봉우리 조합마다 다익스트라 수행
• 호출 횟수: $25,000 \times 25,000 = 625,000,000$ (6억 2,500만 번)
• 결과: 시간 초과 및 메모리 초과

2. 다중 출처 다익스트라

• 모든 출입구를 PQ에 한 번에 넣고 다익스트라 단 1회 수행
• 시간 복잡도: $O((V + E) \log V)$
• 결과: 약 0.1초 만에 통과

---

정리

• 출발지가 여러 개이고 어느 곳에서 출발해도 상관없는 최단 거리 문제는 다중 출처 다익스트라가 정답입니다.
• PQ에서 꺼낸 후 dist[pIdx] = pVal;을 다시 작성할 필요가 없습니다. pq.offer를 하는 시점에 dist[nextIdx] = nextVal로 미리 업데이트되기 때문입니다.