[Inflearn] 자바 알고리즘 문제풀이 #09-07 7. 원더랜드(최소 스패닝 트리 - 크루스칼 : Union&Find 이용)

설명

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

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

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

위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.

 

입력 

첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.

다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.

 

출력 

모든 도시를 연결하면서 드는 최소비용을 출려한다.

 

예시 입력 1 

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

예시 출력 1

196

 

 

 

 

내 풀이 = 선생님 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    public int v1, v2, 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;
    }
}

public class Main9_7_1 {
    public 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) {
        Main9_7_1 T = new Main9_7_1();
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        unf = new int[v+1];
        for (int i = 1; i <= v; i++) unf[i] = i;
        ArrayList<Edge> arr = new ArrayList<>();
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            arr.add(new Edge(a, b, c));
        }

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

최소비용 신장트리란?

가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 방법을 찾는 알고리즘

조건 1) 모든 노드를 방문하고, 사이클이 없어야 한다.

조건 2) 최소한 n-1개의 간선으로 구성된 그래프이다.

 

최소 비용이기 때문에 cost를 기준으로 오름차순으로 정렬하는 게 가장 먼저여야 한다 !

그 후 연결되지 않은 노드를 선택하면서 연결시켜 주면 된다

 

 

 

결과