[프로그래머스 알고리즘 고득점 Kit][완전탐색][Java] 전력망을 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

프로그래머스 - 전력망을 둘로 나누기

문제 핵심

• 노드 n개, 간선(wires) n-1개 → 트리 구조
• 트리에서 간선 하나를 제거하면 항상 정확히 2개의 컴포넌트로 나뉜다
• 각 간선을 제거했다고 가정하고, 나뉜 두 그룹의 노드 개수 차이가 최소가 되는 경우를 찾는 문제

풀이 전략

1. 인접 리스트 구성: wires를 이용해 양방향 그래프를 List<Integer>[]로 만든다
2. 간선을 하나씩 제거해보며 BFS
   • wires를 순회하면서 매번 간선 [u, v]를 "제거 대상"으로 정한다
   • u에서 BFS를 시작하되, 탐색 도중 u-v 간선만 타지 않도록 조건을 걸어준다
   • 이렇게 하면 u가 속한 그룹의 노드 개수(cnt)를 구할 수 있다
3. 반대쪽 그룹 개수는 계산으로 처리
   • 트리는 간선 제거 시 정확히 2개로 나뉘므로, v가 속한 그룹의 개수는 n - cnt
   • 별도로 v에서 BFS를 또 돌릴 필요가 없다
4. 차이의 최솟값 갱신
   • 두 그룹의 차이 = |cnt - (n - cnt)| = |2*cnt - n|
   • 모든 간선에 대해 이 값을 구해서 최솟값을 갱신

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        List<Integer>[] graph = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for(int[] edge: wires) {
            int u = edge[0];
            int v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        
        int ans = 111;
        for(int[] edge: wires) {
            int u = edge[0];
            int v = edge[1];
            
            int cnt = bfs(u, graph, n, u, v);
            ans = Math.min(ans, Math.abs(2 * cnt - n));
        }
        
        return ans;
    }
    
    public int bfs(int start, List<Integer>[] graph, int n, int u, int v) {
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        
        int cnt = 1;
        q.add(start);
        visited[start] = true;      

        while(!q.isEmpty()) {
            int curr = q.poll();

            
            for(int next : graph[curr]) {
                if(u == curr && v == next) continue;
                if(v == curr && u == next) continue;
                if(visited[next]) continue;
                
                q.add(next);
                cnt++;

                visited[next] = true;     
            }
        }
        
        return cnt;
    }
}

배운 점 / 주의할 점

• 인접 리스트 배열 크기: 노드 번호가 1~n이면 배열 크기는 n+1로 잡아야 함
• BFS 방문 체크 위치: visited는 큐에 넣기 전에 체크해야 중복 삽입을 막을 수 있음 (poll 직후 체크하면 이미 늦음)
• 간선 하나 제외하기: 인접 리스트를 실제로 수정/복구하지 않고, BFS 탐색 중 "지금 이동하려는 간선이 제외 대상인지"만 조건으로 체크하면 충분
• 전체 노드 수를 활용: 두 그룹으로 쪼개지는 구조를 알고 있다면, 한쪽만 세고 나머지는 n - cnt로 계산해서 BFS 호출 횟수를 절반으로 줄일 수 있음

최근에 쉬운 문제만 골라서 풀었더니 실수도 많았고 간단한 것도 어렵게 접근해서 (간선을 이차원boolean 배열로 선택을 관리하려 했다거나, 나머지 그룹 노드 수는 어떻게 구하지 오래 고민했다거나...) 오래 걸렸다.

시간복잡도

• 간선 개수만큼(n-1개) BFS를 도니까 O(V+E) BFS를 n-1번 → 전체적으로 O(n²) 수준 (n이 100 이하라 충분히 통과)