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

💡 풀이

• 끊을 전선 하나씩 고르고 그 전선 제외하고 인접 리스트 생성(createList)
• 생성 후 인접 리스트에 전선 정보 넣기 -> bfs 실행
• bfs 실행해서 노드 수 count하고 두 전력망의 송전탑 개수 차이를 반환
• 가장 작은 차이가 정답

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        for(int i = 0; i<wires.length; i++){
            createList(n);
            
            // 해당 전선(wires[i]) 제외하고 인접 리스트에 넣기
            for(int j = 0; j<wires.length; j++){
                if (j == i) continue;
                int[] curr = wires[j];
                graph.get(curr[0]).add(curr[1]);
                graph.get(curr[1]).add(curr[0]);
            }
            // bfs 실행
            answer = Math.min(checkBfs(n), answer);
        }
        return answer;
    }
    
    // 인접 리스트 생성
    public void createList(int n){
        graph = new ArrayList<>();
        for(int i = 0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
    }
    
    public int checkBfs(int n){
        int cnt = 1;
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n+1];
        
        q.add(1);
        visited[1] = true;
       
        while(!q.isEmpty()){
            int curr = q.poll();
            for(int i : graph.get(curr)){
                if(!visited[i]){
                    q.add(i);
                    visited[i] = true;
                    cnt++;
                }
            }
        }
        // cnt : bfs로 찾은 노드 count 
        // 두 전력망 차이 반환
        return Math.abs(2 * cnt - n);
    }
}