[programmers/java] 부대복귀 - Dijkstra로 여러 출발지의 최단 경로를 계산

1. 문제 개요

- url : https://school.programmers.co.kr/learn/courses/30/lessons/132266

 

그래프가 주어졌을 때, 여러 개의 출발지(source) 노드에서 하나의 도착지(destination)까지의 최단 경로를 각각 구해야 하는 상황이 종종 발생한다.

---

2. 비효율적인 접근: 출발지마다 Dijkstra 수행

for (int source : sources) {
    runDijkstra(source, destination);
}

위 방식은 출발지가 K개일 경우 총 K회의 Dijkstra를 실행하게 된다. 노드 수를 V, 간선 수를 E라고 할 때, 전체 시간 복잡도는 다음과 같다.

O(K * (V + E) log V)

출발지의 수가 수십 개 이상일 경우, 현실적인 입력 크기에서는 시간 초과가 발생할 수 있다.

---

3. 최적화 아이디어: 목적지 기준 Dijkstra 단 1회 실행

다익스트라 알고리즘은 방향에 구애받지 않으며, 실제로는 목적지에서 출발지로의 경로를 구하는 것이나 그 반대나 본질적으로 동일하다.

따라서 다음과 같이 목적지에서 출발하여 전체 노드까지의 최단 거리만 한 번 계산하고, 이후 각 source에 대해 거리만 조회하는 방식으로 변경할 수 있다.

---

4. Java 구현 예시

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        // 1. 인접 리스트: Map<노드번호, Map<이웃, 가중치>>
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] road : roads) {
            int from = road[0];
            int to = road[1];
            int weight = 1;

            graph.computeIfAbsent(from, k -> new HashMap<>())
                 .merge(to, weight, Math::min);
            graph.computeIfAbsent(to, k -> new HashMap<>())
                 .merge(from, weight, Math::min);
        }

        // 2. Dijkstra: 목적지에서 전체 노드로의 거리 계산
        int[] dist = dijkstra(n, graph, destination);

        // 3. 결과 구성
        int[] answer = new int[sources.length];
        for (int i = 0; i < sources.length; i++) {
            answer[i] = dist[sources[i]] == Integer.MAX_VALUE ? -1 : dist[sources[i]];
        }

        return answer;
    }

    // 목적지에서 모든 노드로의 거리 계산
    private int[] dijkstra(int n, Map<Integer, Map<Integer, Integer>> graph, int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            if (curr.time > dist[curr.region]) continue;

            for (Map.Entry<Integer, Integer> entry :
                    graph.getOrDefault(curr.region, Collections.emptyMap()).entrySet()) {
                int next = entry.getKey();
                int cost = curr.time + entry.getValue();

                if (cost < dist[next]) {
                    dist[next] = cost;
                    pq.offer(new Node(next, cost));
                }
            }
        }

        return dist;
    }

    class Node implements Comparable<Node> {
        int region;
        int time;

        Node(int region, int time) {
            this.region = region;
            this.time = time;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.time, o.time); // 최소 힙
        }
    }
}