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

📌 핵심 요약

• 트리의 성질 — 노드 n개, 간선 n-1개면 트리. 간선 하나를 끊으면 정확히 두 개의 컴포넌트로 갈라진다.
• 완전탐색으로 충분 — n ≤ 100이라 간선 99개를 전부 끊어봐도 여유롭게 통과한다. 그리디하게 고민할 필요가 없다.
• 한쪽만 세면 끝 — 한쪽 크기가 count면 반대쪽은 n - count. 차이는 Math.abs(count - (n - count)).
• 트리라서 가능한 단순화 — 간선을 끊는 대신 반대편 노드 하나를 차단하는 것으로 같은 효과를 낼 수 있다.

 

목차

1 문제 소개

Programmers #86971

전력망을 둘로 나누기

2 ≤ n ≤ 100 · 간선 n-1개

난이도: Lv.2

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있다. 전선 중 하나를 끊어 전력망을 2개로 분할하려고 한다. 이때 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고, 그 개수 차이(절댓값)를 반환하는 문제다.

풀이 과정

1. wires 배열로 양방향 인접 리스트를 만든다.
2. 간선을 하나씩 "끊었다고 가정"하며 전부 시도한다 (완전탐색).
3. 끊은 간선의 한쪽 끝에서 BFS를 돌려 그쪽 컴포넌트의 크기 count를 센다. 이때 반대편 노드를 차단해 간선을 끊은 효과를 낸다.
4. Math.abs(count - (n - count))로 두 그룹의 차이를 구하고 최솟값을 갱신한다.

2 접근 아이디어

노드 n개 + 간선 n-1개 = 트리

문제를 읽고 처음 눈에 들어온 건 "송전탑 n개, 전선 n-1개"라는 조건이었다. 이건 그래프 이론에서 아주 특별한 형태, 바로 트리라는 뜻이다. 사이클이 없는 연결 그래프이기 때문에, 트리에서 간선 하나를 끊으면 정확히 두 개의 덩어리로 갈라진다는 게 보장된다. 

완전탐색으로 충분한 이유

n이 최대 100이므로 간선은 최대 99개다.

"간선을 하나씩 끊어보고 → 매번 결과를 확인"하는 완전탐색을 해도 간선 99개 × 탐색 O(n) 수준이라 시간은 전혀 문제가 되지 않는다.

어떤 간선을 끊어야 유리할지 그리디하게 고민할 필요 없이, 전부 끊어보면 된다.

한쪽 크기만 세면 반대쪽은 공짜

전체가 n개인데 한쪽이 count개라면, 나머지는 자동으로 n - count개다.

그래서 BFS는 한 번만 돌리면 되고, 두 그룹의 차이는 아래 한 줄로 정리된다.

ℹ️

차이 계산과 Math.abs가 필요한 이유

count - (n - count)는 count가 작은 쪽 덩어리인지 큰 쪽 덩어리인지에 따라 음수가 될 수 있다. 문제가 원하는 건 부호 없는 "차이"이므로 Math.abs로 절댓값을 씌운다. 이게 없으면 음수 diff가 Math.min에서 부당하게 이겨버려 답이 망가진다. 

3 BFS 설계 — 간선 대신 노드를 차단하기

트리라서 가능한 단순화

"간선 (a, b)를 끊는다"를 구현하는 가장 정직한 방법은 BFS 중에 a→b, b→a 양방향 이동을 모두 검사해서 막는 것이다.

그런데 트리에서는 더 단순한 방법이 있다. a에서 출발하는 BFS가 b 쪽 덩어리로 건너가는 통로는 그 간선 하나뿐이므로, "b 노드 자체를 밟지 않는다"는 조건 하나로 간선을 끊은 것과 완전히 같은 효과가 난다.

⚠️

이 단순화는 트리에서만 성립한다

사이클이 있는 일반 그래프라면 b로 우회해서 도달하는 다른 경로가 존재할 수 있다. 그 경우 노드 차단은 간선 차단보다 더 많은 것을 막아버려 결과가 달라진다. 일반 그래프 문제에서는 간선 쌍(a, b)을 양방향으로 검사하는 방식을 써야 안전하다.

BFS의 핵심: 확인 → 도장 → 예약

BFS에서 큐에 넣는다는 건 "나중에 방문할 것을 예약한다"는 뜻이다. 그래서 visited의 실제 의미는 "방문 완료"가 아니라 "큐에 들어간 적 있음(예약됨)"이고, 도장은 큐에 넣는 시점에 찍어야 한다. 순서는 항상 이 세 동작이 한 세트다.

• 확인 — !visited[next] 아직 예약 안 된 노드인지 검사한다.
• 도장 — visited[next] = true 즉시 예약됨 표시를 남긴다.
• 예약 — queue.add(next) 그 다음에 큐에 넣는다.

🚨

직접 겪은 실수: 방문 확인을 빼먹으면 무한 루프

처음 작성한 코드에서 visited[next] = true로 표시는 했지만 넣기 전에 이미 방문한 노드인지 확인을 안 했다. 양방향 그래프에서는 노드 1과 2가 서로를 계속 다시 큐에 넣는 핑퐁이 벌어져서, count가 틀리는 정도가 아니라 while문이 영원히 끝나지 않는다. 표시만 하고 확인을 안 하면 표시가 아무 역할을 못 한다는 걸 몸으로 배웠다.

4 전체 코드 (Java)

 

Java — Solution.java

import java.util.*;

class Solution {

    // 여러 메서드에서 함께 쓰기 위해 필드로 선언
    private List<List<Integer>> graph;

    public int solution(int n, int[][] wires) {
        int answer = n; // 어떤 diff도 n 이상이 될 수 없으므로 n으로 초기화

        // 1. 인접 리스트 구성 (인덱스 = 노드 번호, 0번은 버림 칸)
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] wire : wires) {
            graph.get(wire[0]).add(wire[1]);
            graph.get(wire[1]).add(wire[0]); // 무방향이므로 양방향 등록
        }

        // 2. 간선을 하나씩 끊어보며 완전탐색
        for (int[] wire : wires) {
            // wire[0]에서 시작, wire[1] 노드를 차단
            int count = bfs(wire[0], wire[1], n);

            // 3. 두 그룹의 크기 차이로 최솟값 갱신
            int diff = Math.abs(count - (n - count));
            answer = Math.min(answer, diff);
        }

        return answer;
    }

    // start에서 출발하되 blocked 노드로는 이동하지 않는 BFS
    private int bfs(int start, int blocked, int n) {
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        // 4. 시작 노드를 예약(큐 삽입)하고 도장 찍기
        queue.add(start);
        visited[start] = true;
        int count = 0;

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

            for (int next : graph.get(cur)) {
                // 5. 차단 노드이거나 이미 예약된 노드면 패스
                if (next == blocked || visited[next]) continue;

                visited[next] = true;
                queue.add(next);
            }
        }

        // 6. start 쪽 컴포넌트의 크기 반환
        return count;
    }
}

5 시간복잡도

BFS 한 번은 노드와 간선을 모두 훑으므로 O(V+E) = O(n)이고, 전체는 O(n²)이다.

n ≤ 100이므로 최악에도 1만 번 수준의 연산이라 아주 여유롭다.

단계	연산	복잡도	비고
그래프 구성	간선 n-1개를 양방향 등록	O(n)	1회
BFS 1회	컴포넌트 크기 세기	O(n)	여유
전체	간선 수 × BFS	O(n²)	n ≤ 100이라 충분

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.