[프로그래머스] 전력망을 둘로 나누기(86971)

1. 문제 풀이 아이디어

• 연결 중 하나를 끊고 BFS를 수행하여 두 트리의 노드 개수 차이를 계산한 후, 그 최소값을 구해 문제를 해결한다.

2. 나의 정답 코드

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        boolean[][] graph = new boolean[n + 1][n + 1];
        for (int[] w : wires) {
            graph[w[0]][w[1]] = true;
            graph[w[1]][w[0]] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (!graph[i][j]) continue;
                boolean[][] temp = new boolean[n + 1][];
                for (int k = 1; k <= n; k++) {
                    temp[k] = Arrays.copyOf(graph[k], n + 1);
                }
                temp[i][j] = false;
                temp[j][i] = false;
                answer = Math.min(check(n, temp), answer);
            }
        }
        return answer;
    }

    private int check(int n, boolean[][] graph) {
        int[] result = new int[2];
        boolean[] visited = new boolean[n + 1];
        int index = 0;
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            int count = 0;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                count++;
                for (int j = 1; j <= n; j++) {
                    if (!graph[cur][j] || visited[j]) continue;
                    visited[j] = true;
                    queue.add(j);
                }
            }
            result[index] = count;
            index++;
        }
        return Math.abs(result[0] - result[1]);
    }
}

3. 정리

• 전선 연결 정보를 2차원 배열로 저장한다.

• for문을 통해 모든 연결을 하나씩 제거하여 임시 배열(temp)을 생성하고 이를 check 메서드로 전달한다.

• check 메서드에서 BFS를 이용해 각각의 트리 크기를 계산하여 result 배열에 저장하고, 두 크기의 차의 절대값을 반환한다.

• 반환된 차이값을 answer와 비교하여 최소값으로 갱신한다.

• 최종적으로 최소값을 반환하여 문제를 해결한다.