99클럽 코테 스터디 36일차 TIL - [프로그래머스] 전력망을 둘로 나누기 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 전력망을 둘로 나누기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/86971

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 송전탑의 개수 n, 전선 정보가 담긴 정수 2차원 배열 wires
출력 : 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

가능한 시간복잡도

O(n^2)

알고리즘 선택

BFS

📌 코드 설계하기

1. 인접 리스트를 이용해 그래프를 생성하고, 간접 정보를 인접 리스트에 추가한다.
2. 간선을 하나씩 제거하면서 그래프가 두 부분으로 나뉘었을 때의 노드 수를 계산한다.
3. BFS를 사용해 한쪽 서브트리의 노드 수를 계산한다.
4. 두 서브트리의 노드 수 차이를 계산하고, 최소값을 업데이트한다.
5. 다음 계산을 위해 제거했던 간선을 다시 복구한다.
6. 모든 간선에 대해 위의 작업을 반복한 후, 가장 작은 크기 차이를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        int answer = n;

        // 그래프를 인접 리스트로 표현
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보를 인접 리스트에 추가
        for (int[] wire : wires) {
            int u = wire[0];
            int v = wire[1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        // 각 간선을 하나씩 끊어보며 최소 차이를 계산
        for (int[] wire : wires) {
            int u = wire[0];
            int v = wire[1];

            // 간선을 끊음
            graph.get(u).remove((Integer) v);
            graph.get(v).remove((Integer) u);

            // BFS나 DFS로 한쪽 네트워크의 크기 계산
            int count = bfs(graph, n, u);

            // 두 네트워크 크기의 차이 계산
            int diff = Math.abs(n - 2 * count);
            answer = Math.min(answer, diff);

            // 끊었던 간선 다시 복구
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        return answer;
    }

    // BFS를 이용하여 한쪽 네트워크의 노드 수 계산
    private int bfs(List<List<Integer>> graph, int n, int start) {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }

        return count;
    }
}