[ 프로그래머스 / JAVA / Level 2 ] 전력망을 둘로 나누기

제출한 코드

import java.util.*;

class Solution {
    static int max;
    
    public int solution(int n, int[][] wires) {
        int answer = -1;
        int[][] map = new int[n+1][n+1];
        
        max = Integer.MAX_VALUE;
        // 초기 세팅
        for(int[] edge : wires){
            map[edge[0]][edge[1]] = 1;
            map[edge[1]][edge[0]] = 1;
        }
        
        // 간선을 1개씩 제거해보면서 탐색 진행
        for(int[] edge : wires){
            map[edge[0]][edge[1]] = 0;
            map[edge[1]][edge[0]] = 0;
            
            logic(map, n);
            map[edge[0]][edge[1]] = 1;
            map[edge[1]][edge[0]] = 1;
        }
        
        answer = max;
        return answer;
    }
    private static void logic(int[][] map, int n){
        Deque<Integer> q = new ArrayDeque<>();
        List<Integer> count = new ArrayList<>();
        boolean[] v = new boolean[n+1];
        
        // 연결된 송전탑 수 구하기
        for(int i = 1 ; i < n ; i++){
            if(v[i]){
                continue;
            }
            int cnt = 0;
            v[i]=true;
            q.add(i);
            
            // BFS
            while(!q.isEmpty()){
                int cur = q.poll();
                cnt ++;
                
                for(int j = 1; j <= n ; j++){
                    if(map[cur][j] == 1 && !v[j]){
                        v[j] = true;
                        q.add(j);
                    }
                }
            }
            
            // 송전탑 개수 저장
            count.add(cnt);
        }
        
        // 정답 갱신
        if(count.size() > 1){
            max = Math.min(max, Math.abs(count.get(0)-count.get(1)));
        }
    }
}

---

생각한 로직

 

1. 2차원 배열에 간선 정보를 저장한다.

2. 간선을 1개만 제거하고 2구역의 송전탑 수를 구한다.

3. BFS를 이용해 송전탑을 전체 순회하면서 2구역의 수를 구한다.

4. 송전탑 개수의 차이 ( 절대값 ) 이 최소인 경우 max를 갱신한다.