[BFS] 프로그래머스 전력량을 둘로 나누기(실패 분석 - 시간부족)

접근

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

BFS의 전형적인 문제입니다.
컴퓨터와 연결된 네트워크의 수를 구하는 문제와 비슷합니다.

하지만 이 문제는 무조건 두 개의 네트워크를 만들어야 하고
네트워크에 연결된 송전탑의 개수 차이가 적도록 하는 문제입니다.

따라서 모든 송전탑은 연결되어져 있기 때문에
BFS 시작할 때 처음 넣어주는 Queue의 원소는 임의의 아무 송전탑을 넣어도 상관없습니다.

어차피 하나의 전선을 끊으면 두개의 네트워크로 나눠지는 것이 전제로 깔려있기 때문에 어느 송전탑에서 시작해서 하나의 네트워크와 연결된 송전탑의 개수를 구할 수 있습니다.

풀이

import java.util.*;
class Solution {
    
    static boolean[] visited ;
    static boolean[][] tower;
    
    
    public int solution(int n, int[][] wires) {
        int answer = -1;
       
        tower = new boolean[n+1][n+1];
        
        for(int i=0;i<n-1;i++){
            int a = wires[i][0];
            int b = wires[i][1];
            tower[a][b]=true;
            tower[b][a]=true;
        }
        
        int min = Integer.MAX_VALUE;
        
        //하나씩 전선 끊기
        for(int i=0;i<wires.length;i++){
            //1. 끊을 전선 a와 b사이
            int a = wires[i][0];
            int b = wires[i][1];
            
            visited = new boolean[n+1];
            
            //2. 전선을 끊기 위해서 false
            tower[a][b]=false;
            tower[b][a]=false;
            //3. bfs를 통해서 끊었을 때의 한쪽 송전탑 개수
            int cnt = bfs(wires,n);
            //4. 반대편 송전탑 개수
            int next_cnt = n-cnt;
            //5. 양쪽 송전탑의 차이를 최솟값과 비교하여 저장
            min = min> Math.abs(cnt-next_cnt)?  Math.abs(cnt-next_cnt):min;
            //6. 다시 연결          
            tower[a][b]=true;
            tower[b][a]=true;
            
        }
        
        
        return min;
    }
    
    static int bfs(int[][] wires, int n){
        int cnt=1;
        Queue<Integer> q = new LinkedList<>();
        //1. 어차피 트리이기 때문에 무조건 연결 따라서 1번 송전탑을 처음에 넣는다.
        q.add(1);
        visited[1]=true;
        while(!q.isEmpty()){
            int p = q.poll();
            for(int i=1;i<=n;i++){
                //2. 해당 송전탑과 연결되어져 있고 들린적이 없는 송전탑이라면
                if(tower[p][i]==true && visited[i] == false){
                    cnt++;
                    visited[i]=true;
                    q.add(i);
                }
            }   
        }
        
        return cnt;
        
        
    }
    
}