Lv 2. 전력망을 둘로 나누기

 

코드 흐름

• 우선 wires에 담긴 모든 연결 정보를 인접 배열 형태로 나타낸다.
• 이후 wires에 담긴 정보를 순회하면서 그정보에 대하여 끊어주고
  • 끊은 이후 BFS 탐색하여 몇개가 연결되어있는지 확인한다.
  • answer와 비교하여 차이가 최소인지 확인하고
  • 다시 끊었던 정보에 대해 연결을 진행하고 다음  wires에 담긴 정보로 넘어가 반복한다.

import java.util.*;

class Solution {
    int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        arr = new int[n+1][n+1];
        
        for(int i = 0 ; i < wires.length; i++){
            arr[wires[i][0]][wires[i][1]]=1;
            arr[wires[i][1]][wires[i][0]]=1;
        }
        int a, b;
        for(int i = 0; i < wires.length; i++){
            a = wires[i][0];
            b = wires[i][1];
            
            arr[a][b] = 0;
            arr[b][a] = 0;
            
            answer = Math.min(answer,bfs(n,a));
            
            arr[a][b] = 1;
            arr[b][a] = 1;
            
        }
        
        return answer;
    }
    public int bfs(int n, int start){
        boolean[] visit= new boolean[n+1];
        int cnt=1;
        
        Queue<Integer> queue= new LinkedList<>();
        queue.offer(start);
        
        while(!queue.isEmpty()){
            int point= queue.poll();
            visit[point]= true;
            
            for(int i=1; i<=n; i++){ 
                if(visit[i]) continue;
                if(arr[point][i]==1) {
                    queue.offer(i);
                    cnt++;
                }
            }
        }
        return (int)Math.abs(n-2*cnt);
    }
}