[JAVA] 백준 1922 - 네트워크 연결

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

package DAY06.P1922;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Computer implements Comparable<Computer>{
    int start, end, cost;

    public Computer(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Computer o){
        return this.cost - o.cost;
    }
}
public class Main {
    static int[] parent;
    public static int find(int v){
        if(parent[v] == v) return v;
        else return parent[v] = find(parent[v]);
    }
    public static void union(int a, int b){
        int fa = find(a);
        int fb = find(b);
        if(fa!=fb) parent[fa] = fb;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        ArrayList<Computer> list = new ArrayList<>();
        parent = new int[n+1];

        for(int i=1; i<=n; i++) parent[i] = i;

        while(m-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.add(new Computer(a, b, c));
        }
        Collections.sort(list); // 가중치 오름차순 정렬

        int ans = 0;
        for(Computer c : list){ // 가중치가 작은 것부터 순회
            int rootStart = find(c.start);
            int rootEnd = find(c.end);

            if(rootStart!=rootEnd){ // 연결하는 두 노드의 루트 노드가 다르면 사이클이 아님
                union(c.start, c.end); // 두 노드 연결
                ans+=c.cost; // 최소 비용 선택
            }
        }
        System.out.println(ans);
    }
}

 

 

최소스패닝트리를 구하는 문제이다. 크루스칼 알고리즘을 사용했다. 

 

 

스패닝 트리: 그래프 내의 모든 정점을 포함하는 트리.  트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.

최소 스패닝 트리: 스패닝 트리에서 사용된 간선의 가중치 합이 최소인 트리