자바 코딩테스트 강좌, 최소 신장 트리 구하기

안녕하세요! 오늘은 알고리즘 시험에서 자주 출제되는 최소 신장 트리(Minimum Spanning Tree) 문제에 대해 알아보겠습니다. 특히, 자바로 이 문제를 해결하는 방법을 심층적으로 다뤄볼 것입니다.

문제 설명

다음과 같은 가중치가 있는 연결 그래프가 있다고 가정해봅시다. 이 그래프의 모든 정점이 연결되어 있으며, 가중치는 서로 다릅니다. 여러분의 목표는 이 그래프의 최소 신장 트리를 구하는 것입니다.

입력 형식

첫 번째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다.
다음 E개의 줄에는 각 간선의 두 정점과 가중치 u, v, w가 주어진다.

출력 형식

최소 신장 트리를 구성하는 간선의 목록과 그 가중치의 합을 출력하시오.

예제 입출력

입력 예시

출력 예시

        1 - 2
        2 - 3
        총 가중치: 3

문제 풀이 접근 방식

최소 신장 트리를 찾기 위해 사용되는 대표적인 알고리즘에는 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim’s Algorithm)이 있습니다. 여기서는 크루스칼 알고리즘을 이용하여 이 문제를 풀어보겠습니다.

크루스칼 알고리즘 개요

간선을 가중치에 따라 오름차순으로 정렬한다.
가장 작은 가중치의 간선을 선택하고, 사이클이 생기지 않는다면 이 간선을 결과에 포함시킨다.
위 과정을 반복하여 모든 정점이 연결될 때까지 진행한다.

자바 코드 구현

이제 실제로 자바 코드를 통해 크루스칼 알고리즘을 구현해보겠습니다.


import java.util.Arrays;

public class Kruskal {
    static class Edge implements Comparable {
        int u, v, weight;

        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    static int[] parent;
    static int[] rank;

    public static void main(String[] args) {
        int V = 3; // 정점의 개수
        int E = 3; // 간선의 개수
        Edge[] edges = new Edge[E];

        edges[0] = new Edge(1, 2, 1);
        edges[1] = new Edge(2, 3, 2);
        edges[2] = new Edge(1, 3, 3);

        Arrays.sort(edges);

        parent = new int[V + 1];
        rank = new int[V + 1];

        for (int i = 1; i <= V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        int totalWeight = 0;
        System.out.println("최소 신장 트리의 간선:");
        for (Edge edge : edges) {
            if (union(edge.u, edge.v)) {
                System.out.println(edge.u + " - " + edge.v);
                totalWeight += edge.weight;
            }
        }
        System.out.println("총 가중치: " + totalWeight);
    }

    static int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    static boolean union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
            return true;
        }
        return false;
    }
}

코드 설명

위 코드에서는 다음의 주요 기능들이 구현되어 있습니다:

Edge 클래스: 간선을 나타내는 클래스로, 가중치 기준으로 비교 가능하도록 설정되어 있습니다.
find 메서드: 유니온 파인드(Union-Find) 알고리즘을 통해 루트 노드를 찾아 반환합니다. 경로 압축(Path Compression)을 통해 성능을 향상시킵니다.
union 메서드: 두 정점의 루트 노드가 다르면 합치고, 성공적으로 합쳐졌는지 여부를 반환합니다. 이를 통해 사이클을 체크합니다.

테스트 및 실행

이 코드를 컴파일하고 실행시키면, 다음과 같은 결과가 출력됩니다:

최소 신장 트리의 간선:
1 - 2
2 - 3
총 가중치: 3

최소 신장 트리에 대한 응용

최소 신장 트리는 다양한 분야에서 활용될 수 있습니다. 예를 들어:

네트워크 설계: 컴퓨터 네트워크를 설계할 때 최소 비용으로 연결 가능한 경로를 결정할 때 유용합니다.
도로망 구축: 도시의 도로망을 최소 비용으로 구축할 때 사용될 수 있습니다.
전력망 설계: 전력망의 비용 절감을 위해 신장 트리 알고리즘이 활용됩니다.

결론

오늘은 최소 신장 트리 문제를 크루스칼 알고리즘을 통해 해결하는 방법에 대해 알아보았습니다. 이 알고리즘은 시간 복잡도가 O(E log E)로, 간선의 개수에 비례하여 효율적입니다. 알고리즘 문제 해결을 위한 준비 과정에서 이와 같은 문제를 여러 번 연습해보시길 권장합니다. 앞으로 여러분의 코딩 테스트 준비에 도움이 되길 바랍니다!