PROGRAMMERS_Lv2_전력망을 둘로 나누기

📁 [Lv2_86971] 전력망을 둘로 나누기

    class Solution {
        static int[][] map;
        static boolean[][] v;
        public int solution(int n, int[][] wires) {
            int answer = -1;

            map = new int[n][n];


            // 등록하기
            for(int i=0; i<wires.length; i++){
                int start = wires[i][0] -1;
                int end = wires[i][1] -1;

                map[start][end] = 1;
                map[end][start] = 1;
            }

            int min = Integer.MAX_VALUE;

            for(int i=0; i<wires.length; i++){
                int start = wires[i][0] -1;
                int end = wires[i][1] -1;

                // 연결 끊기
                map[start][end] = 0;
                map[end][start] = 0;


                // 최솟값 구하기
                min = Math.min(min, bfs(start, n));

                // 백트래킹
                map[start][end] = 1;
                map[end][start] = 1;
            }


            answer = min;
            return answer;
        }

        // bfs
        static int bfs(int start, int n){
            Queue<Integer> q = new LinkedList<>();
            q.add(start);
            int cnt = 1;
            v = new boolean[n][n];

            while(!q.isEmpty()){
                int point = q.poll();
                for(int i=0; i<n; i++){
                    if(map[point][i] == 1 || map[i][point] == 1){
                        if(!v[i][point] && !v[point][i]){
                            cnt++;
                            v[i][point] = true;
                            v[point][i] = true;
                            q.add(i);
                        }
                    }
                }
            }
            return Math.abs(cnt - (n-cnt));
        }
    }

🤔 나의 생각

완탐 + bfs 문제로 풀었는데 너무 오래걸렸다.
포인트는 하나의 줄을 끊었을 때 2개로 나뉘는 것과 하나의 부분만 구해주고 나머지는 전체값에서 구해준 횟수를 빼주면 된다.
그리고 bfs 탐색하는 시작점도 start 부분을 모두 탐색하는 것