전력망을 둘로 나누기

[pagh2322]

문제 링크

[pagh2322]

매번 전선을 하나 고른뒤, 해당 전선을 제외한 나머지 전선으로 2개의 트리를 만들어요. find 연산과 union 연산을 통해 2개의 트리를 만들 수 있으며, 각 트리의 크기 차이가 제일 작은 값을 구하면 돼요.

코드

class Solution {

    int[] parent;

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        int len = wires.length;
        for (int i = 0; i < len; i++) {
            init(n);
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    continue;
                }
                union(wires[j][0], wires[j][1]);
            }

            int count1 = 1, count2 = 0;
            int temp = find(1);
            for (int j = 2; j <= n; j++) {
                if (temp == find(j))
                    count1++;
                else
                    count2++;
            }
            answer = Math.min(answer, Math.abs(count1 - count2));
        }

        return answer;
    }

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

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

    void union(int a, int b) {
        int aRoot = find(a), bRoot = find(b);
        if (aRoot == bRoot)
            return;
        parent[bRoot] = aRoot; 
    }

}