[백준] 1197 최소 스패닝 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 1

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1

3

풀이

일반적인 MST 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Edge implements Comparable<Edge>{
    int a;
    int b;
    int dist;

    public Edge(int a, int b, int dist){
        this.a = a;
        this.b = b;
        this.dist = dist;
    }
    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.dist, o.dist);
    }
}
public class Main {

    static int V;
    static int E;
    static int[] parent;
    static ArrayList<Edge> eList;
    static int sum;

    static int findP(int x){
        if(parent[x] != x) return parent[x] = findP(parent[x]);
        return parent[x];
    }

    static void union(int n1, int n2){
        int p1 = findP(n1);
        int p2 = findP(n2);

        if(p1 < p2){
            parent[p2] = p1;
        }
        else if(p2 < p1){
            parent[p1] = p2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        parent = new int[V+1];
        for(int i = 1; i <= V; i++) parent[i] = i;
        eList = new ArrayList<>();
        sum = 0;

        for(int i = 1; i <= E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            eList.add(new Edge(a, b, c));
        }
        eList.sort(null);

        // 가중치 작은 것부터 union
        for(int i = 0; i < eList.size(); i++){
            Edge e = eList.get(i);
            if(findP(e.a) != findP(e.b)){
                union(e.a, e.b);
                sum += e.dist;
            }
        }

        // 최소 가중치 합 출력
        System.out.println(sum);
    }

}