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

https://campus.programmers.co.kr/courses/15436/lessons/132841?language=java 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    static int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = n;
        arr= new int[n+1][n+1];
        
        //1. 서로 연결되어 있는 송전탑을 찾기
        for(int i=0; i<wires.length; i++){
            arr[wires[i][0]][wires[i][1]]=1;
            arr[wires[i][1]][wires[i][0]]=1;
        }
        
        //2. 선을 하나씩 끊어보며 순회
        int a, b;
        for(int i=0; i<wires.length; i++){
            a= wires[i][0];  //연결되어 있는 송전탑 번호 구별
            b= wires[i][1];  
            
            //전선을 끊고
            arr[a][b]=0;
            arr[b][a]=0;
            
            //bfs
            answer= Math.min(answer, bfs(n, a));  //넓이탐색
            
            //선 다시 복구
            arr[a][b]=1;
            arr[b][a]=1;
        }
        
        return answer;
    }
    
    public int bfs(int n, int start){  //전체 송전탑개수 시작점을 메개변수로 받기
        int[] visit= new int[n+1];
        int cnt=1;
        
        Queue<Integer> queue= new LinkedList<>();
        queue.offer(start);
        
        while(!queue.isEmpty()){ //큐가 비워지지 않으면
            int point= queue.poll();
            visit[point]= 1; //미리 시작점을 체크 해두기
            
            for(int i=1; i<=n; i++){ //point와 연결된 애들 중에 방문한적 없는 노드 전부 큐에 넣기
                if(visit[i]==1) continue;  //방문했으면 넘기기
                if(arr[point][i]==1) {  // 인접했다면
                    queue.offer(i); 인접한 송전탑 번호를 queue에 넣고
                    cnt++;  //카운트 올림
                }
            }
        }
        return (int)Math.abs(n-2*cnt); //cnt-(n-cnt);
    }//bfs
}

 

프로그래머스

이문제에서는 송전탑의 전선을 끊는다는 개념이 미리 체크를 걸어 놓고 넓이 탐색을 하는 것이 핵심이다

예를 들어 3번송전탑과 4번 송전탑의 전선을 끊는다면 3번 송전탑을 미리 체크를 걸어두고 그것을 큐에다 담고 반복문으로 3번 송전탑과 인접한 송전탑을 넓이 탐색으로 전부 다 찾은 후에 전체 송전탑의 개수에서 3번송전탑+3번송전탑과 인접한 송전탑을 모두 더한 값을 빼버리고 그것을 최소값으로 비교시킨다면 답이 나온다