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

문제

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

프로그래머스

 

코드

import java.util.*;
class Solution {
    static ArrayList<Integer> arr [];
    public int solution(int n, int[][] wires) {

        arr = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            arr[i] = new ArrayList<>();
        }
        
        int answer = Integer.MAX_VALUE;

        for(int i=0;i<n-1;i++){
            for(int k=1;k<=n;k++){
                arr[k] = new ArrayList<>();
             }
            for(int j=0;j<n-1;j++){
                if(i == j) continue;
                arr[wires[j][0]].add(wires[j][1]);
                arr[wires[j][1]].add(wires[j][0]);
            }
            int count = bfs(n);
            answer = Math.min(answer, count);
        }
        
        
        return answer;
        
    }
    
    public int bfs(int n){
        
        int count [] = new int [2];
        int idx = 0;
        boolean visited [] = new boolean[n+1];
        Queue<Integer> que = new LinkedList<>();
        for(int i=1;i<=n;i++){
            if(visited[i]) continue;
            que.add(i);
            visited[i]=true;
            count[idx] = 1;
            
            while(!que.isEmpty()){
                int cur = que.poll();
                for(int next : arr[cur]){
                    if(visited[next]) continue;
                    que.add(next);
                    visited[next] = true;
                    count[idx] += 1;
                }
            }
            idx++;
            
        }
        return Math.abs(count[1] - count[0]);
    }
}