[JAVA 문제 풀이] 367. 전력망을 둘로 나누기

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = n; // 최소 차이를 저장할 변수, 최대값으로 시작

        // 모든 전선을 하나씩 끊어보며 반복
        for (int i = 0; i < wires.length; i++) {
            // 인접한 노드를 담는 리스트 초기화
            // int[i][j] 일때 i번 노드와 연결된 노드를 j에 저장
            List<List<Integer>> node = new ArrayList<>();
            for (int j = 0; j <= n; j++) {
                node.add(new ArrayList<>());
            }

            // i번째 전선을 끊고 나머지로 인접리스트 구성
            for (int j = 0; j < wires.length; j++) {
                if (i == j)
                    continue; // 끊을 전선은 무시
                int a = wires[j][0];
                int b = wires[j][1];
                node.get(a).add(b); // 양방향 연결
                node.get(b).add(a);
            }

            // 끊은 전선 중 한 쪽 노드에서 BFS로 연결된 송전탑 개수 세기
            int count = bfs(node, n, wires[i][0]);

            /* 각 집합 A와 B의 송전탑 개수를 count와 n - count로 정의
             * |A - B| = |count - (n - count)|
             *         = |2 * count - n|
             *         = |n - 2 * count|
             */
            int diff = Math.abs(n - 2 * count);
            answer = Math.min(answer, diff); // 최소 차이 갱신
        }

        return answer;
    }

    // BFS로 한 쪽 전력망에 연결된 송전탑 개수 세는 함수
    private int bfs(List<List<Integer>> node, int n, int start) {
        boolean[] visited = new boolean[n + 1]; // 방문 체크 배열
        Queue<Integer> queue = new LinkedList<>(); // BFS용 큐

        visited[start] = true; // 시작 노드 방문 처리
        queue.offer(start);
        int count = 1; // 시작 노드 포함

        while (!queue.isEmpty()) {
            int current = queue.poll(); // 현재 노드 꺼냄

            // 인접 노드 순회
            for (int next : node.get(current)) {
                if (!visited[next]) { // 방문하지 않은 노드면
                    visited[next] = true;
                    queue.offer(next); // 큐에 추가
                    count++; // 개수 증가
                }
            }
        }

        return count; // 연결된 노드 수 반환
    }
}