[BOJ][6497] 전력난 - JAVA

참고 : https://www.acmicpc.net/submit/6497

로그인

 

참고 풀이 링크 : https://steady-coding.tistory.com/118

[BOJ] 백준 6497번 : 전력난 (JAVA)

 

 - 크루스칼 알고리즘 사용하는 문제

 - 크루스칼은 개념적으로만 알고 있었고 union-find 의 개념을 몰랐다.

 - Minimum Spanning Tree 공부 좀 더 해야 할 듯 하다.

 - 모든 노드를 연결하면서 최소한의 비용을 가지는 tree를 만들어야 함. (모든 노드가 연결 = 모든 길의 전신주에 불이 들어 옴)

 

import java.util.*;

class Solution {
    static int[] parent;
    static ArrayList<Edge> edges;

    static class Edge {
        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if (m == 0 && n == 0) {
                break;
            }

            edges = new ArrayList<Edge>();

            int totalCost = 0;

            for (int i = 0; i < n; i++) {
                int e1 = sc.nextInt();
                int e2 = sc.nextInt();
                int weight = sc.nextInt();
                edges.add(new Edge(e1, e2, weight));
                totalCost += weight;
            }
            edges.sort(Comparator.comparingInt(a -> a.weight));

            parent = new int[m];
            for (int i = 0; i < m; i++) {
                parent[i] = i;
            }

            int minCost = 0;

            for (int i = 0; i < edges.size(); i++) {
                Edge e = edges.get(i);

                if (find(e.start) != find(e.end)) {
                    minCost += e.weight;
                    union(e.start, e.end);
                }
            }

            System.out.println(totalCost - minCost);

        }

    }

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

        return parent[a] = find(parent[a]);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (parent[a] != parent[b]) {
            parent[b] = a;
        }
    }
}