[알고리즘] 코테 유형 분석 20. 최소 신장 트리

안녕하세요 이번 시간에는 최소 신장 트리에 대해 알아보는 시간을 갖도록 하겠습니다.

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 간선들의 가중치의 합을 최소로 하는 트리입니다. 여기서 포인트는 모든 노드를 연결할 때의 가중치의 합을 구하는데 사용된다는 점입니다. 앞서 살펴본 다른 알고리즘의 경우 시작점에서 도착점까지의 값 하나를 얻는다고 할 때 최소 신장 트리를 구현하면 모든 노드가 연결되었을 때 최소 가중치의 합을 구할 수 있습니다.

여기서 주의할 점은 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다는 점입니다. 사이클은 사이클이 아닌 모든 노드가 연결된 그래프보다 필요 없는 간선이 1개 더 존재하기 때문입니다. 따라서 N개의 노드가 있으면 최소 신장 트리를 구성하는 간선의 개수는 항상 N-1개가 되며, 사이클을 체크하기 위해 유니온 파인드 알고리즘을 사용합니다.

최소 신장 트리 구현 순서는 다음과 같습니다.
1. 간선 클래스 구현(시작, 도착, 가중치)
2. 우선 순위 큐에 간선 클래스를 저장(ProirityQueue)하고 유니온 파인드 대표 노드 배열 초기화(parent[i] = i)
--> 이 때 우선 순위 큐는 가중치 기준으로 오름차순 정렬
3. 우선 순위 큐가 빌 때까지 유니온 파인드 진행
--> 시작 노드의 대표 노드와 도착 노드의 대표 노드가 다르다면 다른 노드이기 때문에 최소 신장 트리로 연결하고 가중치 합에 현재 간선을 누적, 지나온 간선 수++
4. 총 간선 비용 출력

백준 1197(최소 스패닝 트리) 문제를 이용하여 직접 구현해보겠습니다. 그래프가 주어졌을 때 그 그래프의 최소 신장 트리를 구하는 프로그램으로 위에서 언급한 순서대로 구현합니다.

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

class Main{
    static int N,M;
    static int[] parent;
    static PriorityQueue<Edge> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parent = new int[N+1];
        for(int i=0;i<=N;i++) parent[i] = i;

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            queue.add(new Edge(s,e,v));
        }

        int result = 0;
        while(!queue.isEmpty()){
            Edge curr = queue.poll();
            if(find(curr.s) != find(curr.e)){
                union(curr.s, curr.e);
                result += curr.v;
            }
        }
        System.out.println(result);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a < b) parent[b] = a;
        else parent[a] = b;
    }

    static int find(int a){
        if(a == parent[a]) return a;
        else return parent[a] = find(parent[a]);
    }

    static class Edge implements Comparable<Edge>{
        int s;
        int e;
        int v;

        Edge(int s, int e, int v){
            this.s = s;
            this.e = e;
            this.v = v;
        }

        @Override
        public int compareTo(Edge o){
            return this.v - o.v;
        }
    }
}

최소 신장 트리는 하나의 사이클로 연결된 그래프에서 하나의 노드에서 다른 노드까지의 모든 간선의 합의 최솟값을 구하고 싶은 경우 사용됩니다.

백준 1414(불우이웃돕기) 문제의 경우 집 안의 N개의 컴퓨터를 모두 연결할 때 기부할 수 있는 랜선의 길이의 최댓값을 구하는 문제입니다. 기부할 수 있는 랜선의 길이의 최댓값은 곧 연결할 랜선의 최솟값을 구하는 문제이기 때문에 최소 신장 트리를 구현합니다. 현재 연결된 총 랜선을 구한 후 최소 신장 트리 내의 지나온 간선의 누적합과의 차를 출력합니다. 이 때 지나온 간선의 수가 N-1이 아니라면 -1을 출력합니다.

백준 17472(다리 만들기2) 문제의 경우 모든 섬을 연결하는 다리 길이의 최솟값을 구하는 문제입니다. DFS로 각 섬에 아이디를 부여하여 각 아이디 별 섬의 리스트의 리스트를 생성합니다.(List<List>) 이후 각 리스트를 탐색하면서 각 섬에서 4방향으로 직선으로 쭉 이동해서 다른 섬이 나오면 현재까지의 다리 길이를 간선의 가중치로 저장하여 최소 신장 트리를 이용하여 간선의 누적합의 최솟값, 즉 다리 길이의 최솟값을 구합니다.