원더랜드(최소스패닝트리-크루스칼)

도시를 연결하는 도로의 최소비용 찾기

 

도시의 개수 V와 도로의 개수 E가 주어진다

 

입력

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

 

최소스패닝트리, 크루스칼 알고리즘 등등으로 부르고

내가 이해한건 시작노드, 끝나는 노드, 비용을 가지는 Edge 클래스를 만들어서 비용을 기준으로 오름차순으로 정렬한

arraylist에 edge를 넣고, 시작노드와 끝 노드가 연결됐는지를 유니온파인드로 판단해 노드를 연결한 집합을 만들면서

연결할때마다 비용을 저장해두는 걸로 이해했다

 

!유니온 파인드는 그냥 방법을 외우자

unf[] <- 인덱스 = 값인 배열

union - find로 같은 집합인지 비교해서 아니면 같은 집합으로 unf를 수정

find - unf[v]가 v랑 값이 다르면 find(unf[v])를 재귀적으로 불러서 값을 찾는 함수, return unf[v] = find(unf[v]); 형태로

unf에 값을 저장하면서 그래프를 압축시킨다

 

전체 노드가 집합이 이루어진 트리 형태가 되면 for문을 돌 필요가 없어진다, 노드가 연결될때마다 값을 증가시키는 tmp변수를 만들어두고 tmp == n-1(n개의 노드로 트리를 만들면 간선은 n-1이 최대)이 되면 for문을 break 하면 된다 

 

 

import java.util.*;

class Edge implements Comparable<Edge>{
    int v1, v2, cost;

    //cost 순으로 오름차순 정렬
    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }

    Edge(int v1,int v2, int cost){
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
}

class Main{
    static int res = 0;
    static int[] unf;
    static ArrayList<Edge> arr;

    public static int find(int v){
        if (v == unf[v]) return v;
        //unf[v]의 값을 저장해두면서 그래프를 압축
        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) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        unf = new int[n+1];
        arr = new ArrayList<>();
        //unf배열 부모값 초기화
        for (int i = 1; i <= n; i++) unf[i] = i;
        for (int i =0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            arr.add(new Edge(a, b, c));
        }
        //arr에 있는 m개의 정점과 정점사이 간선이 비용이 적은 순서대로 정렬된다
        Collections.sort(arr);
        //비용이 적은 순서대로 정점을 돌면서 이미 집합이 아니면 아직 이어지지 않은 트리니 결과에 더해준다
        for (Edge ob : arr){
            if (find(ob.v1) != find(ob.v2)){
                union(ob.v1, ob.v2);
                res += ob.cost;
            }
        }
        System.out.println(res);

    }
}