[코드트리] 다익스트라 알고리즘 쉽게 이해하기 (개념부터 구현까지 총정리)

1. 다익스트라 알고리즘은 무엇일까?

다익스트라 알고리즘은 그래프 내의 한 정점(시작점)에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.

현실 세계에서 내비게이션이 목적지까지의 최소 시간 경로나 최소 비용 경로를 찾을 때 사용하는 알고리즘의 뼈대가 되기도 합니다. 단, 이 알고리즘은 간선의 가중치가 음수가 아닐 때만 정상적으로 동작한다는 중요한 제약 조건이 있습니다. 음수 간선이 존재할 경우에는 벨만-포드(Bellman-Ford) 알고리즘을 사용해야 합니다.

2. 동작 과정

다익스트라 알고리즘은 '매 순간 가장 비용이 적은 노드를 선택한다'는 그리디(Greedy) 알고리즘과, '이전에 계산해둔 최단 거리 값을 활용한다'는 동적 계획법(DP)의 아이디어가 결합되어 있습니다.

기본적인 동작 과정은 다음과 같습니다.

1. 초기화: 출발 노드를 설정하고, 출발 노드에서 출발 노드로 가는 거리는 0, 나머지 모든 노드로 가는 거리는 무한대(Infinity)로 설정합니다.
2. 최소 거리 노드 선택: 아직 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택합니다. (처음에는 출발 노드가 선택됩니다.)
3. 인접 노드 거리 갱신: 선택된 노드를 거쳐서 그 인접 노드로 가는 거리를 계산합니다. 만약 새로 계산된 거리가 기존에 저장된 인접 노드의 최단 거리보다 짧다면, 그 값을 갱신해 줍니다.
4. 방문 처리: 선택된 노드는 방문 처리를 하여 더 이상 최단 거리가 갱신되지 않도록 확정합니다.
5. 반복: 모든 노드를 방문할 때까지 2~4번 과정을 반복합니다.

3. 다익스트라 코드 O(V^2)

가장 직관적인 방식은 매번 반복문을 돌며 아직 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선형 탐색으로 찾는 방식입니다. 정점의 개수가 V일 때, 매번 V개의 노드를 탐색하므로 시간 복잡도는 O(V^2)가 됩니다.

정점의 개수가 5,000개 이하일 때는 충분히 사용할 수 있지만, 그 이상 넘어가면 시간 초과가 발생할 수 있습니다.

import java.util.*;

public class DijkstraBasic {
    static final int INF = (int) 1e9;
    static int n, m;
    static int[][] graph;
    static int[] dist;
    static boolean[] visited;

    public static void main(String[] args) {
        // n: 정점의 개수 (예: 5)
        n = 5;
        graph = new int[n + 1][n + 1];
        dist = new int[n + 1];
        visited = new boolean[n + 1];

        // 그래프 및 최단 거리 배열 초기화
        for (int i = 1; i <= n; i++) {
            Arrays.fill(graph[i], INF);
            dist[i] = INF;
        }

        // 예시 간선 세팅 (graph[출발][도착] = 비용)
        graph[1][2] = 2;
        graph[1][3] = 5;
        graph[2][3] = 1;
        graph[2][4] = 2;
        graph[3][5] = 3;
        graph[4][5] = 1;

        dijkstra(1); // 1번 노드에서 출발
    }

    static void dijkstra(int start) {
        dist[start] = 0;

        for (int i = 0; i < n; i++) {
            int minDist = INF;
            int minIdx = -1;

            // 1. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 찾기
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIdx = j;
                }
            }

            // 도달할 수 있는 노드가 없으면 종료
            if (minIdx == -1) break;

            // 2. 방문 처리
            visited[minIdx] = true;

            // 3. 인접 노드 거리 갱신
            for (int j = 1; j <= n; j++) {
                if (graph[minIdx][j] != INF) {
                    if (dist[j] > dist[minIdx] + graph[minIdx][j]) {
                        dist[j] = dist[minIdx] + graph[minIdx][j];
                    }
                }
            }
        }
    }
}

4. 우선순위 큐를 이용한 최적화 O(E log V)

O(V^2) 방식의 단점은 '최소 거리를 가진 노드'를 찾기 위해 매번 모든 노드를 훑어야 한다는 점입니다. 이를 해결하기 위해 최소 힙(Min Heap) 구조인 우선순위 큐(Priority Queue)를 도입합니다.

우선순위 큐를 사용하면 가장 거리가 짧은 노드를 찾는 데 걸리는 시간을 O(log V)로 단축할 수 있습니다. 간선의 개수를 E라고 할 때, 전체 시간 복잡도는 O(E log V)가 되어 정점의 개수가 10만 개 이상인 큰 그래프에서도 빠르게 최단 거리를 구할 수 있습니다. 코딩 테스트에서는 대부분 이 방식을 요구합니다.

import java.util.*;

public class DijkstraPQ {
    static class Node implements Comparable<Node> {
        int index, distance;

        Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        // 거리가 짧은 것이 높은 우선순위를 가지도록 설정
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.distance, o.distance);
        }
    }

    static final int INF = (int) 1e9;
    static int n;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] dist;

    public static void main(String[] args) {
        n = 5;
        dist = new int[n + 1];
        Arrays.fill(dist, INF);

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 예시 간선 세팅
        graph.get(1).add(new Node(2, 2));
        graph.get(1).add(new Node(3, 5));
        graph.get(2).add(new Node(3, 1));
        graph.get(2).add(new Node(4, 2));
        graph.get(3).add(new Node(5, 3));
        graph.get(4).add(new Node(5, 1));

        dijkstra(1);
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int now = current.index;
            int currentDist = current.distance;

            // 이미 처리된 노드라면 무시 (큐에 남아있는 예전의 긴 거리 정보 폐기)
            if (dist[now] < currentDist) continue;

            // 인접 노드 확인
            for (Node next : graph.get(now)) {
                int cost = dist[now] + next.distance;

                // 거리가 더 짧게 갱신되는 경우에만 큐에 삽입
                if (cost < dist[next.index]) {
                    dist[next.index] = cost;
                    pq.offer(new Node(next.index, cost));
                }
            }
        }
    }
}

5. 천 개의 정거장

위에서 배운 우선순위 큐 다익스트라 알고리즘을 활용할 수 있는 코드트리 문제입니다.

• 문제 링크: 코드트리 - 천 개의 정거장

이 문제의 특징은 단순히 최단 '비용(거리)'만 구하는 것이 아니라, 비용이 같을 경우에는 '거쳐간 정거장의 수'가 최소가 되도록 두 가지 조건을 모두 고려해야 한다는 점입니다.

문제 접근 방법

1. 다중 조건 우선순위 큐 구현: 비용과 정거장 수를 함께 관리하는 객체를 만들고, Comparable 인터페이스를 구현하여 1순위: 비용 오름차순, 2순위: 정거장 수 오름차순으로 큐가 정렬되도록 합니다.
2. 거리 배열(DP 테이블) 고도화: 단순히 dist 배열에 비용 하나만 저장하는 것이 아니라, 특정 정거장에 도달했을 때의 (비용, 정거장 수) 쌍 자체를 기록하여 더 나은 조건일 때만 갱신하도록 설계합니다.
3. 메모리 초과(MLE) 방지를 위한 간선 전처리: 모든 버스 노선마다 나올 수 있는 출발지-도착지 쌍을 일일이 리스트에 객체로 추가하면, 최악의 경우 수억 개의 간선 객체가 생성되어 메모리가 터지게 됩니다. 정점 수가 1000개로 고정되어 있으므로, edgeCost와 edgeTime 2차원 배열을 두어 중복 간선들 중 가장 최적인 간선 하나만 압축해서 남기는 과정이 필수적입니다.

풀이 코드 요약

import java.util.*;
import java.io.*;

public class Main {
    static class Route implements Comparable<Route> {
        int node;
        long cost;
        int time; // 거쳐간 정거장의 수

        Route(int node, long cost, int time) {
            this.node = node;
            this.cost = cost;
            this.time = time;
        }

        @Override
        public int compareTo(Route o) {
            // 1순위: 비용이 작은 순
            if (this.cost != o.cost) {
                return Long.compare(this.cost, o.cost);
            }
            // 2순위: 정거장 수가 작은 순
            return Integer.compare(this.time, o.time);
        }
    }

    static int a, b, n;
    static ArrayList<ArrayList<Route>> graph = new ArrayList<>();
    static long[] minCost;
    static int[] minTime;
    
    // 중복 간선을 최적화하기 위한 2차원 배열 (메모리 초과 방지)
    static long[][] edgeCost = new long[1001][1001];
    static int[][] edgeTime = new int[1001][1001];
    static final long INF = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= 1000; i++) {
            graph.add(new ArrayList<>());
            Arrays.fill(edgeCost[i], INF);
            Arrays.fill(edgeTime[i], Integer.MAX_VALUE);
        }

        minCost = new long[1001];
        minTime = new int[1001];
        Arrays.fill(minCost, INF);
        Arrays.fill(minTime, Integer.MAX_VALUE);

        // n개의 버스 노선 정보 입력 및 간선 전처리
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long cost = Long.parseLong(st.nextToken());
            int stopCount = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            int[] stops = new int[stopCount];
            for (int j = 0; j < stopCount; j++) {
                stops[j] = Integer.parseInt(st.nextToken());
            }

            // 모든 정거장 쌍에 대해 최적의 비용과 시간만 2차원 배열에 남김 (객체 생성 최소화)
            for (int j = 0; j < stopCount; j++) {
                for (int k = j + 1; k < stopCount; k++) {
                    int u = stops[j];
                    int v = stops[k];
                    int t = k - j;
                    
                    if (cost < edgeCost[u][v]) {
                        edgeCost[u][v] = cost;
                        edgeTime[u][v] = t;
                    } else if (cost == edgeCost[u][v] && t < edgeTime[u][v]) {
                        edgeTime[u][v] = t;
                    }
                }
            }
        }

        // 전처리된 2차원 배열을 바탕으로 실제 그래프 리스트 구성 (최대 100만 개 이하의 간선)
        for (int i = 1; i <= 1000; i++) {
            for (int j = 1; j <= 1000; j++) {
                if (edgeCost[i][j] != INF) {
                    graph.get(i).add(new Route(j, edgeCost[i][j], edgeTime[i][j]));
                }
            }
        }

        dijkstra(a);

        if (minCost[b] == INF) {
            System.out.println("-1 -1");
        } else {
            System.out.println(minCost[b] + " " + minTime[b]);
        }
    }

    static void dijkstra(int start) {
        PriorityQueue<Route> pq = new PriorityQueue<>();
        pq.offer(new Route(start, 0, 0));
        minCost[start] = 0;
        minTime[start] = 0;

        while (!pq.isEmpty()) {
            Route cur = pq.poll();
            int now = cur.node;

            // 기존에 기록된 최적값보다 비용이 더 크거나, 비용은 같은데 정거장 수가 더 많으면 스킵
            if (minCost[now] < cur.cost || (minCost[now] == cur.cost && minTime[now] < cur.time)) {
                continue;
            }

            for (Route next : graph.get(now)) {
                long nextCost = cur.cost + next.cost;
                int nextTime = cur.time + next.time;

                // 새로운 경로가 비용이 더 저렴하거나, 비용은 같지만 거치는 정거장 수가 더 적을 경우 갱신
                if (nextCost < minCost[next.node] || (nextCost == minCost[next.node] && nextTime < minTime[next.node])) {
                    minCost[next.node] = nextCost;
                    minTime[next.node] = nextTime;
                    pq.offer(new Route(next.node, nextCost, nextTime));
                }
            }
        }
    }
}

이처럼 다익스트라 알고리즘은 단순히 거리 값을 하나 관리하는 것에서 나아가 여러 가지 조건을 동시에 만족하는 최적화 문제로 응용할 수 있습니다.

https://www.codetree.ai/ko/trail-info

코딩 테스트 학습 안내 | 코드트리