[Do It! 코딩테스트 자바편(김종관)] 문제 064(백준 1197번)

느낀점

• 첫 시도에 풀 수 있었던 문제

문제

최소 스패닝 트리 (백준: 1197번)

풀이

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

public class Main {
    static int nodeCnt, edgeCnt;
    static PriorityQueue<Edge> edgeList = new PriorityQueue<>();
    static int[] parent;

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

        for (int i = 1; i <= edgeCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            edgeList.add(new Edge(s, e, value));
        }

        parent = new int[nodeCnt + 1];
        for (int i = 1; i <= nodeCnt; i++) {
            parent[i] = i;
        }

        int result = mst();
        System.out.println(result);
    }

    private static int mst() {
        int sumValue = 0;
        int nowEdgeCnt = 0;
        while (nowEdgeCnt < nodeCnt - 1) {
            Edge now = edgeList.poll();
            int s = now.s;
            int e = now.e;
            int value = now.value;

            if (find(s) != find(e)) {
                union(s, e);
                sumValue += value;
                nowEdgeCnt++;
            }
        }

        return sumValue;
    }

    private static void union(int s, int e) {
        int root_s = find(s);
        int root_e = find(e);

        if (root_s != root_e) {
            parent[root_s] = root_e;
        }
    }

    private static int find(int index) {
        if (index == parent[index]) {
            return index;
        } else {
            return parent[index] = find(parent[index]);
        }
    }
}

class Edge implements Comparable<Edge> {
    int s;
    int e;
    int value;

    public Edge(int s, int e, int value) {
        this.s = s;
        this.e = e;
        this.value = value;
    }

    @Override
    public int compareTo(Edge e) {
        return this.value - e.value;
    }

}