자바 코딩테스트 강좌, 다익스트라

이번 포스트에서는 다익스트라 알고리즘에 대해 알아보고, 이를 활용한 문제를 풀어보도록 하겠습니다. 다익스트라 알고리즘은 그래프의 각 정점 간의 최단 경로를 구하는 알고리즘으로, 주로 다양한 경로 탐색 문제에 사용됩니다.

1. 알고리즘 이해하기

다익스트라 알고리즘은 가중치가 있는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 효율적인 방법입니다. 이 알고리즘은 특정 정점에 도달할 때까지의 경로 길이를 계산하고, 최단 경로를 지속적으로 업데이트하는 방식으로 작동합니다.

1.1. 기본 개념

가중치 그래프: 각 간선에 비용 또는 가중치가 부여된 그래프.
우선순위 큐: 현재까지의 최단 경로를 관리하기 위해 사용합니다.
탐욕적 방식: 현재 발견된 최단 경로를 바탕으로 더 짧은 경로를 찾아가는 방식.

2. 문제 제시

문제 설명

주어진 가중치 그래프에서 시작 정점과 도착 정점 사이의 최단 경로를 구하는 문제입니다. 그래프는 정점의 수와 간선의 수가 주어지고, 각 간선의 가중치도 함께 제공됩니다.

입력

첫째 줄: 정점의 수 N (1 ≤ N ≤ 1000)
둘째 줄: 간선의 수 M (1 ≤ M ≤ 10000)
셋째 줄: 시작 정점 S, 도착 정점 E
이후 M개의 줄: 각 간선의 시작 정점 A, 끝 정점 B, 가중치 W (1 ≤ A, B ≤ N, 1 ≤ W ≤ 10000)

출력

시작 정점 S에서 도착 정점 E까지의 최단 경로 길이를 출력합니다. 만약 도달할 수 없다면 -1을 출력합니다.

3. 코드 작성

3.1. 자바 코드

import java.util.*;

public class Dijkstra {
    static class Edge {
        int to;
        int weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 그래프 구성
        int N = scanner.nextInt(); // 정점 수
        int M = scanner.nextInt(); // 간선 수
        int S = scanner.nextInt(); // 시작 정점
        int E = scanner.nextInt(); // 도착 정점

        List[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 입력 받기
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            int W = scanner.nextInt();
            graph[A].add(new Edge(B, W));
            graph[B].add(new Edge(A, W)); // 무향 그래프
        }

        // 다익스트라 알고리즘 실행
        int result = dijkstra(graph, N, S, E);
        System.out.println(result);
    }

    public static int dijkstra(List[] graph, int N, int start, int end) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.offer(new Edge(start, 0));

        boolean[] visited = new boolean[N + 1];

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.to;

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            for (Edge edge : graph[currentNode]) {
                if (visited[edge.to]) continue;

                if (dist[currentNode] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[currentNode] + edge.weight;
                    pq.offer(new Edge(edge.to, dist[edge.to]));
                }
            }
        }

        return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
    }
}

3.2. 코드 설명

위 코드는 Java로 작성된 다익스트라 알고리즘의 구현입니다. 다음은 주요 부분에 대한 설명입니다:

Edge 클래스: 그래프의 간선을 정의하는 클래스입니다. 각 간선은 목적지 노드와 가중치를 가지고 있습니다.
그래프 초기화: 인접 리스트 방식으로 그래프를 초기화합니다.
우선순위 큐: 현재 최단 경로를 탐색하기 위해 사용됩니다. 더 짧은 거리의 노드를 우선적으로 처리합니다.
다익스트라 알고리즘: 매 반복에서 가장 작은 거리를 가진 노드를 선택하고 해당 노드에 연결된 노드들의 거리를 업데이트합니다.

4. 시간 복잡도

다익스트라 알고리즘의 시간 복잡도는 우선순위 큐의 사용 여부에 따라 달라집니다. 배열을 우선순위 큐로 사용할 경우 O((N + M) log N)입니다. 여기서 N은 정점의 수, M은 간선의 수입니다. 이 알고리즘은 적은 간선 수에 비해 정점이 많은 그래프에서 좋은 성능을 보입니다.

5. 마무리

이번 포스트에서는 다익스트라 알고리즘을 이용한 최단 경로 문제를 해결하는 방법에 대해 알아보았습니다. 이 알고리즘은 다양한 분야에서 활용될 수 있으며, 특히 네트워크, 지도 서비스, 최적화 문제에서 많이 사용됩니다. 코딩 테스트에서 이러한 알고리즘에 대한 이해와 문제 해결 능력은 매우 중요하니, 연습을 꾸준히 하시는 것을 추천드립니다.