[Java] 2021 위클리 챌린지 9주차 - 전력망을 둘로 나누기

Node라는 클래스를 만들어서 wire로 연결된 송전탑들을 연결을 시켜준다. 

이후 어떤 wire를 제거하였을 때, 차가 최소가 되는지 모르기 때문에 각 wire들을 순회하면서 제거한다. 

그리고 bfs를 이용해서 각 송전탑들이 몇개가 연결이 되었는지 구하고, 두 그룹의 차이를 출력하면 된다.

class Node {
    int id;
    List<Node> children;

    public Node(int id) {
        this.id = id;
        children = new ArrayList<>();
    }
}

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = n;
        Node[] nodeArr = new Node[n + 1];
        for (int i = 0; i <= n; i++) {
            nodeArr[i] = new Node(i);
        }
        for (int i = 0; i < n - 1; i++) {
            nodeArr[wires[i][0]].children.add(nodeArr[wires[i][1]]);
            nodeArr[wires[i][1]].children.add(nodeArr[wires[i][0]]);
        }

        for (int i = 0; i < n - 1; i++) {
            // i번째 wire를 제거한다.
            nodeArr[wires[i][0]].children.remove(nodeArr[wires[i][1]]);
            nodeArr[wires[i][1]].children.remove(nodeArr[wires[i][0]]);

            List<Integer> groupSize = new ArrayList<>();
            Set<Integer> visited = new HashSet<>();

            for (int j = 1; j <= n; j++) {
                if (!visited.contains(j)) {
                    Queue<Node> q = new LinkedList<>();
                    q.add(nodeArr[j]);
                    visited.add(j);
                    int size = 1;
                    while (!q.isEmpty()) {
                        Node front = q.poll();
                        for (int k = 0; k < front.children.size(); k++) {
                            int id = front.children.get(k).id;
                            if (!visited.contains(id)) {
                                visited.add(id);
                                q.add(nodeArr[id]);
                                size++;
                            }
                        }
                    }
                    groupSize.add(size);
                }
            }

            answer = Math.min(Math.abs(groupSize.get(0) - groupSize.get(1)), answer);

            // 분리한 i번째 wire를 다시 연결한다.
            nodeArr[wires[i][0]].children.add(nodeArr[wires[i][1]]);
            nodeArr[wires[i][1]].children.add(nodeArr[wires[i][0]]);
        }

        return answer;
    }
}