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

문제 풀이

성공 여부(걸린 시간): 성공(27분 40초)

아이디어

연결된 엣지를 하나씩 끊어보며 양 전력망의 개수를 구한다.
그다음 해당 개수를 result 리스트에 넣고 탐색을 마쳤을 때
전력망이 두개라면 두 전력망의 개수의 차이를 구한다.
간단히 말하면 각 엣지가 끊어진 경우마다 비교해서 최소의 차이의 절대값을 구한다 이다.

백준에 있는 이장선거? 개리멘더링? 그거랑 비슷한 문제인듯

풀이 코드

import java.util.*;
class Solution {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean [] visited;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        // 그래프 연결
        for(int [] wire: wires){
            graph.get(wire[0]).add(wire[1]);
            graph.get(wire[1]).add(wire[0]);
        }
        //하나씩 끊어보기 
        for(int [] wire: wires){
            visited = new boolean[n+1];
            List<Integer> result = new ArrayList<>();
            for(int i=1; i<=n; i++){
                if(!visited[i]){
                    int count = BFS(i, wire);
                    result.add(count);
                }
            }
            if(result.size()==2){
                answer= Math.min(Math.abs(result.get(0)-result.get(1)), answer);
            }

        }
        return answer;
    }
    static int BFS(int start, int [] wire){
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        visited[start] = true;
        int count = 0;
        while(!q.isEmpty()){
            int cur = q.poll();
            count++;
            for(int x: graph.get(cur)){
                if(!visited[x]&&!(cur==wire[0] && x==wire[1])&&!(cur==wire[1] && x==wire[0])){
                    visited[x] = true;
                    q.add(x);
                }
            }
        }
        return count;
    }
}