[백준] 6497: 전력난 JAVA

접근

테스트 케이스의 개수가 정해져있지 않고 0 0이 들어오면 종료한다는 조건 이외에는, 다른 크루스칼 알고리즘들과 동일하다. 

 

 

코드

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

public class BJ6497 {
    static class Edge implements Comparable<Edge> {
        int from, to, cost;

        public Edge(int from, int to, int cost){
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

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

    static int[] root;

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

        while(true){
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());

            // 테스트 케이스 종료
            if(m == 0 && n == 0)
                break;

            PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
            root = new int[m+1];
            for (int i = 0; i < m+1; i++)
                root[i] = i;

            for (int i = 0; i < n; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int z = Integer.parseInt(st.nextToken());

                pq.add(new Edge(x, y, z));
            }
            
            int minCost = kruskal(m, pq);
            sb.append(minCost).append("\n");
        }

        System.out.println(sb);
    }

    private static int kruskal(int m, PriorityQueue<Edge> pq) {
        int res = 0;
        int cnt = 0;

        while(!pq.isEmpty()){
            if(cnt == m-1) break;
            Edge e = pq.poll();

            int r1 = find(e.from);
            int r2 = find(e.to);

            if(r1 == r2){
                res += e.cost;
                continue;
            }

            union(r1, r2);
            cnt++;
        }

        while(!pq.isEmpty()){
            Edge e = pq.poll();
            res += e.cost;
        }

        return res;
    }

    private static void union(int r1, int r2) {
        root[r1] = r2;
    }

    static int find(int n){
        if(root[n] == n) return n;
        return root[n] = find(root[n]);
    }
}