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

1. 최소 신장 트리란?

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 할당된 무방향 그래프에서 모든 정점을 포함하면서 전체 가중치의 합이 최소가 되는 트리를 말합니다. 최소 신장 트리는 네트워크 설계, 클러스터링 및 여러 최적화 문제에 사용됩니다.

2. 알고리즘 개요

최소 신장 트리를 찾기 위한 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim’s Algorithm)이 있습니다. 이 두 가지 알고리즘은 각각 다른 방식으로 MST를 구성합니다.

2.1. 크루스칼 알고리즘

크루스칼 알고리즘은 그래프의 간선을 가중치에 따라 오름차순으로 정렬한 후, 사이클을 형성하지 않도록 간선을 추가하여 MST를 구성하는 방식입니다.

2.2. 프림 알고리즘

프림 알고리즘은 시작 정점에서 출발하여 현재 연결된 정점 중 가장 가중치가 낮은 간선을 선택하여 MST를 확장해 나가는 방식입니다.

2.3. 알고리즘 선택

두 가지 알고리즘 모두 효율적으로 MST를 찾을 수 있지만, 크루스칼은 간선의 수가 적은 희소 그래프에 더 적합하고, 프림은 정점의 수가 적은 밀접 그래프에 적합합니다.

3. 문제 설명

문제: 최소 신장 트리 만들기

가중치가 있는 무방향 그래프가 주어질 때, 최소 신장 트리를 구하시오. 입력은 다음과 같은 형식입니다:

첫 번째 줄에 정점의 수 V와 간선의 수 E가 주어진다.
다음 E개의 줄에 각각 u, v, w가 주어져, 이는 정점 u와 v를 연결하는 가중치 w의 간선을 의미한다.

출력으로 최소 신장 트리의 가중치 합을 출력하시오.

4. 문제 풀이 접근법

문제를 해결하기 위해 다음 단계를 따릅니다:

입력값을 읽어들인다.
간선을 가중치에 따라 정렬한다.
유니온-파인드(Union-Find) 자료구조를 사용하여 사이클을 검출한다.
사이클이 형성되지 않는 간선을 MST에 추가한다.
MST의 가중치 합을 계산하여 출력한다.

5. 자바 코드 구현

5.1. 유니온-파인드 자료구조 구현

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                rank[rootP]++;
            }
        }
    }
}

5.2. 크루스칼 알고리즘 구현

import java.util.*;

class Edge implements Comparable {
    int u, v, weight;

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

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

public class MinimumSpanningTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();
        int E = scanner.nextInt();

        PriorityQueue edgeList = new PriorityQueue<>();
        for (int i = 0; i < E; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int weight = scanner.nextInt();
            edgeList.add(new Edge(u, v, weight));
        }

        UnionFind uf = new UnionFind(V);
        int totalWeight = 0;

        while (!edgeList.isEmpty()) {
            Edge edge = edgeList.poll();
            if (uf.find(edge.u) != uf.find(edge.v)) {
                uf.union(edge.u, edge.v);
                totalWeight += edge.weight;
            }
        }

        System.out.println(totalWeight);
    }
}

6. 코드 설명

위의 코드는 크루스칼 알고리즘을 구현한 것입니다. 먼저, 입력으로 정점의 수와 간선의 수를 읽고 각 간선에 대한 정보를 저장합니다. 이후 간선을 가중치에 따라 정렬하고, 유니온-파인드 자료구조를 사용하여 사이클을 형성하지 않는 간선을 선택합니다. 최종적으로, 선택된 간선의 가중치 합을 출력합니다.

7. 시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 일반적으로 O(E log E)로, 이는 간선 정렬에 대한 복잡도입니다. 유니온-파인드 연산은 매우 효율적이며 거의 상수 시간에 수행됩니다.

8. 마무리

최소 신장 트리는 그래프 이론에서 중요한 개념으로, 다양한 최적화 문제에 활용됩니다. 크루스칼과 프림 알고리즘을 이해하고 구현함으로써 최소 신장 트리를 쉽게 구할 수 있습니다. 이번 강좌를 통해 MST의 개념을 숙지하고, 실제 코딩테스트 문제에 적용할 수 있는 능력을 키우길 바랍니다.