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

문제보기
최소스패닝트리.. 많이 들어보긴 했는데 실제 문제를 풀어본건 처음이다.
늘 얄팍하게만 공부한 탓이다 ㅠ
어쨋든.. 최소스패닝트리란건, 그래프에서 모든 노드를 방문하되 최소비용으로 방문하는것을 말한다.
크루스칼 알고리즘을 알고있다면 쉽게 풀 수 있다. 그리고 크루스칼 알고리즘을 배우기 전에 유니온파인드를 배우면 좋다.

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

class Edge implements Comparable<Edge>{
    int s;
    int e;
    int v;
    Edge(int s, int e, int v){
        this.s = s;
        this.e = e;
        this.v = v;
    }

    @Override
    public int compareTo(Edge o) {
        return this.v - o.v;
    }
}

public class Main {
    static int ip(String s){return Integer.parseInt(s);};
    static int[] roots;

    static boolean hasCircle(int s, int e){
        int sr = getRoot(s);
        int er = getRoot(e);
        if(sr == er) return true;
        else return false;
    }

    static int getRoot(int v){
        if(roots[v] == v ) return v;
        return roots[v] = getRoot(roots[v]);
    }

    static void connect(int s, int e){
        int sr = getRoot(s);
        int er = getRoot(e);
        if(sr < er) roots[er] = sr;
        else roots[sr] = er;
    }

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

        List<Edge> list = new ArrayList<>();

        for(int i = 0 ; i < e ; i++){
            st = new StringTokenizer(br.readLine());
            int start = ip(st.nextToken());
            int end = ip(st.nextToken());
            int value = ip(st.nextToken());
            list.add(new Edge(start, end, value));
        }

        roots = new int[v+1];
        for(int i = 0 ; i <= v ; i++){
            roots[i] = i;
        }

        Collections.sort(list);
        int size = list.size();
        int sum = 0;
        int cnt = 0;
        for(int i = 0 ; i < size ; i++){
            if(cnt == v-1) break;
            Edge edge = list.get(i);
            int start = edge.s;
            int end = edge.e;
            int value = edge.v;
            if(!hasCircle(start, end)){
                connect(start, end);
                sum += value;
                cnt++;
            }
        }
        System.out.println(sum);

    }
}