[Algorithm] 원더랜드_크루스칼 알고리즘(최소스패닝트리)

스패닝 트리란 회로가 존재하지 않도록 그래프의 모든정점을 연결하는 트리이다.

* 회로가 존재한다. == 사이클이 발생한다. == 출발점에서 시작해서 출발점으로 돌아온다. == 그래프

* 아래의 문제 이미지에서 왼쪽 이미지=그래프 / 오른쪽 이미지=트리

 

최소 스패닝 트리(MST)는 스패닝 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 트리를 뜻한다.

 

이번 최소 스패닝 트리 문제는 크루스칼 알고리즘,Union&Find DisjointSet을 이용하여 해결 할 것이다.

---

설명

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.

원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.

아래의 그림은 그 한 예를 설명하는 그림이다.

위의 지도는 각 도시가 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

 

 

 

풀이 과정

1. 간선 리스트를 간선의 가중치를 기준으로 정렬하기 위해 오름차순으로 정렬한다.

2. 가중치가 가장 작은 간선부터  Union & Find이용하여 사이클이 발생하는 간선은 추가 하지 않고 무시하고

사이클이 발생하지 않으면 해당 유지비용을 누적한다.

 

풀이

class Edge implements Comparable<Edge>{
    int v1;
    int v2;
    int cost;
    public Edge(int v1, int v2, int cost){
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }
}

public class Main {
    static int n;
    static int m;
    static int[] unf;
    static int unfCost;

    static void Solution(ArrayList<Edge> arr){
        for(Edge e : arr){
            Union(e.v1, e.v2, e.cost);
        }
        System.out.println(unfCost);
    }

    static int Find(int v){
        if(v == unf[v]){
            return unf[v];
        }else{
            return unf[v] = Find(unf[v]);
        }
    }

    static void Union(int v1, int v2, int cost){
        int fV1 = Find(v1);
        int fV2 = Find(v2);
        if(fV1 != fV2){
            unf[fV1] = unf[fV2];
            unfCost += cost;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ArrayList<Edge> arr = new ArrayList<>();
        unf = new int[n+1];
        for (int i = 0; i <= n; i++) {
            unf[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            arr.add(new Edge(a,b,c));
        }
        Collections.sort(arr);
//        데이터 정렬 확인.
//        for(Edge e : arr){
//            System.out.println(e.v1+" : "+e.v2+" : "+e.cost);
//        }
        Solution(arr);
    }
}

---