[백준/자바] #1197

최소 신장 트리(MST, minimum spanning tree)를 찾는 알고리즘에는 Prim 알고리즘과 Kruskal 알고리즘이 있다고 알고 있는데, 나는 Kruskal 알고리즘을 이용해서 풀었다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

class Main {

    static class Edge implements Comparable<Edge> {
        int u;
        int v;
        int wt;
        public Edge(int u, int v, int wt) {
            this.u = u;
            this.v = v;
            this.wt = wt;
        }
        
        @Override
        public int compareTo(Main.Edge o) {
            if (this.wt < o.wt) {
                return -1;
            } else if (this.wt > o.wt) {
                return 1;
            }
            if (this.u < o.u) {
                return -1;
            } else if (this.u > o.u) {
                return 1;
            }
            if (this.v < o.v) {
                return -1;
            } else if (this.v > o.v) {
                return 1;
            }
            return 0;
        }
    }

    static int V;
    static int E;
    static Edge[] edges;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        String[] input1 = br.readLine().split(" ");
        V = Integer.parseInt(input1[0]);
        E = Integer.parseInt(input1[1]);
        edges = new Edge[E];
        parent = new int[V+1];
        for(int i=0; i<V+1; i++) {
            parent[i] = i;
        }

        for(int i=0; i<E; i++) {
            String[] input2 = br.readLine().split(" ");
            int u = Integer.parseInt(input2[0]);
            int v = Integer.parseInt(input2[1]);
            int wt = Integer.parseInt(input2[2]);
            edges[i] = new Edge(u, v, wt);
        }
        br.close();
        Arrays.sort(edges);

        long answer = findWeight();
        bw.write(String.valueOf(answer) + "\n");

        bw.flush();
        bw.close();
    }

    private static int findParent(int currentNode) {
        if (currentNode == parent[currentNode]) {
            return currentNode;
        }
        parent[currentNode] = findParent(parent[currentNode]);
        return parent[currentNode];
    }

    private static void union(int nodeA, int nodeB) {
        int parentA = findParent(nodeA);
        int parentB = findParent(nodeB);
        if (parentA < parentB) {
            parent[parentB] = parentA;
        } else {
            parent[parentA] = parentB;
        }
    }

    private static long findWeight() {
        long totalWeight = 0L;
        for (Edge edge : edges) {
            int uParent = findParent(edge.u);
            int vParent = findParent(edge.v);
            if (uParent != vParent) {
                union(edge.u, edge.v);
                totalWeight += (long) edge.wt;
            }
        }
        return totalWeight;
    }
}