[카테고리:] 자바 코딩테스트 강좌

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

문제 설명

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

입력 형식

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

출력 형식

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

예제 입출력

        3 3
        1 2 1
        2 3 2
        1 3 3
        

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

문제 풀이 접근 방식

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

크루스칼 알고리즘 개요

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

자바 코드 구현

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

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;
    }
}
    

코드 설명

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

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

테스트 및 실행

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

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

최소 신장 트리에 대한 응용

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

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

결론

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

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. 문제 풀이 접근법

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

1. 입력값을 읽어들인다.
2. 간선을 가중치에 따라 정렬한다.
3. 유니온-파인드(Union-Find) 자료구조를 사용하여 사이클을 검출한다.
4. 사이클이 형성되지 않는 간선을 MST에 추가한다.
5. 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의 개념을 숙지하고, 실제 코딩테스트 문제에 적용할 수 있는 능력을 키우길 바랍니다.