[알고리즘 문제]원더랜드 - 최소스패닝트리 : 크루스칼, Union&Find 활용

▷ 문제

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지
도로는 폐쇄하려고 한다.
아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시
를 연결하는 방법을 찾아낸 것이다.
* 입력
첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의
줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번
도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.
* 출력
모든 도시를 연결하면서 드는 최소비용을 출력한다.

▷ 입력 예시

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

▷ 출력 예시

196

▷ 풀이

import java.util.*;

// 각 정점과 간선을 담는 클래스 생성
class Edge implements Comparable<Edge>{
    public int v1;
    public int v2;
    public int cost;

    Edge(int v1, int v2, int cost){
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Edge ob){
        return this.cost - ob.cost;
    }
}

class Main {
    static int[] unf;
    public static int Find(int v){
        if(v == unf[v]){
            return v;
        } else{
            return unf[v] = Find(unf[v]);
        }
    }
    
    public static void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);

        if(fa != fb){
          unf[fa] = fb;
        }
    }

    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        unf = new int[n+1];
        ArrayList<Edge> arr = new ArrayList<>();

        for(int i=1; i<=n; i++){
            unf[i] = i;
        }

        for(int i=1; i<=m; i++){
            int a = kb.nextInt();
            int b = kb.nextInt();
            int c = kb.nextInt();
            arr.add(new Edge(a, b, c));
        }

        int answer = 0;
        Collections.sort(arr);
        for(Edge ob : arr){
            int fv1 = Find(ob.v1);
            int fv2 = Find(ob.v2);
            if(fv1 != fv2){
                answer += ob.cost;
                Union(ob.v1, ob.v2);
            }
        }

        kb.close();

        System.out.println(answer);
    }
}

▷ 메모

• 그래프는 회로가 존재하며 트리는 존재하지 않는다.
• 트리 간선의 갯수 = 정점의 갯수 - 1
• 때문에 Union & Find을 사용하여 회로가 존재하지 않도록 구현해야 한다.