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

풀이과정

---

송전탑의 수의 차이는 하나가 cnt 개라고 했을 때 다른 구역은 n-cnt 개이다. 두개의 차이는 n-2*cnt의 절대값이다.

따라서 Math.abs(n-2*cnt)를 bfs 함수 내에서 적용시킨 후 리턴해준뒤 각 시행때마다 최소값을 갱신해준다.

그리고 가장 적합한 간선을 자를때는 완전탐색으로 하나하나 간선을 0으로 수정해준뒤 시행해준다.

---

코드

---

import java.util.*;
class Solution {
    static int[][]map;
    public int solution(int n, int[][] wires) {
        int answer = n;
        
        map = new int[n+1][n+1];
        
        
        for(int i = 0;i<wires.length; i++){
            int a = wires[i][0];
            int b = wires[i][1];
            map[a][b] = 1;
            map[b][a] = 1;
        }
        
        for(int i = 0;i<wires.length; i++){
            int a = wires[i][0];
            int b = wires[i][1];
            
            map[a][b] = 0;
            map[b][a] = 0;
            
            answer = Math.min(answer, bfs(n, i+1));
            
            map[a][b] = 1;
            map[b][a] = 1;
        }
        
        
        return answer;
    }
    private int bfs(int n, int start){
        int cnt = 1;
        Queue<Integer>que = new LinkedList<>();
        boolean[] check = new boolean[n+1];
        que.add(start);
        check[start] = true;
        while(!que.isEmpty()){
            int now = que.poll();
            for(int i = 1; i<=n; i++){
                if(map[now][i]==1 && !check[i]){
                    que.add(i);
                    check[i] = true;
                    cnt++;
                }
            }
        }
        
        return (int)Math.abs(n-2*cnt);
    }
}