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

문제

[완전탐색][BFS][Queue]

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

프로그래머스

 

해설

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int[][] graph;
    
    // bfs() : BFS를 통해 송전탑의 개수의 차이(절대값) 계산 
    private int bfs(int n, int start) {
        int[] visited = new int[n+1]; // 노드의 방문여부 확인 배열 
        int count = 1; // 연결된 송전탑의 개수 
        
        Queue<Integer> queue = new LinkedList<Integer>();
        
        visited[start] = 1;
        queue.offer(start);
        
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            
            // 현재 노드와 연결된 노드를 확인하며 큐에 추가 
            for(int i=1; i<=n; i++) {
                if(graph[temp][i] == 1 & visited[i] != 1) {
                    visited[i] = 1;
                    queue.offer(i);
                    count++;
                }
            }
        }
        
        // 네트워크 크기 차이 반환 (한 네트워크 크기 - 다른 네트워크 크기)
        return Math.abs(count - (n - count));
    }
    
    // n : 송전탑의 개수, wires[][] : 전선 정보
    public int solution(int n, int[][] wires) {
        int answer = n;
        graph = new int[n+1][n+1];
        
        // 1. 주어진 선 정보로 그래프 초기화 -> 연결되어진 선은 1로 표시 
        for(int i=0; i< wires.length; i++) {
            int from = wires[i][0], to = wires[i][1];
            graph[from][to] = 1;
            graph[to][from] = 1; 
        }
        
        // 2. 각 선을 하나씩 끊어보며 네트워크 크기 차이의 최솟값을 찾음
        for(int i=0; i<wires.length; i++) {
            int from = wires[i][0], to = wires[i][1];
            
            // 2-1. 선을 끊음
            graph[from][to] = 0;
            graph[to][from] = 0;
            
            // 2-2. 네트워크 크기 차이의 최솟값 갱신
            answer = Math.min(answer, bfs(n, from));
            
            // 2-3. 선을 다시 연결
            graph[from][to] = 1;
            graph[to][from] = 1;
        }
        
        return answer;
    }
}

• 주석 참고 

BFS (너비 우선 탐색) 해설

    // bfs() : BFS를 통해 송전탑의 개수의 차이(절대값) 계산 
    private int bfs(int n, int start) {
        int[] visited = new int[n+1]; // 노드의 방문여부 확인 배열 
        int count = 1; // 연결된 송전탑의 개수 
        
        Queue<Integer> queue = new LinkedList<Integer>();
        
        visited[start] = 1;
        queue.offer(start);
        
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            
            // 현재 노드와 연결된 노드를 확인하며 큐에 추가 
            for(int i=1; i<=n; i++) {
                if(graph[temp][i] == 1 & visited[i] != 1) {
                    visited[i] = 1;
                    queue.offer(i);
                    count++;
                }
            }
        }
        
        // 네트워크 크기 차이 반환 (한 네트워크 크기 - 다른 네트워크 크기)
        return Math.abs(count - (n - count));
    }

• bfs() : 연결된 모든 노드를 방문하여 송전탑의 갯수를 계산함 
• visited[] : 각 노드의 방문 여부를 나타내기 위한 배열 
  • 방문을 했으면 1, 방문을 하지 않았으면 0
• Queue<Integer> queue : bfs를 위한 큐
  • queue.offer(start) : 초기에 시작 노드 start를 큐에 넣음 
• while(!queue.isEmpty()) : 큐가 비어 있을 때까지 반복하여 bfs 수행
• int temp = queue.poll() : 큐에서 하나의 노드를 꺼내서 temp에 저장 
• for(int i=1; i<n; i++) : 현재 노드 (temp) 와 연결된 모든 노드를 확인 
  • if(graph[temp][i] == 1 & visited[i] != 1) : 현재 노드(temp)와 연결되어 있고, 아직 방문하지 않은 노드를 찾음
  • true인 노드를 확인하면 방문 표시 및 큐에 추가 (queue.offer(i))
  • count ++; ( 연결된 송전탑 개수 추가 ) 
• Math.abs(count - (n-count)) : 네트워크 크기 차이를 반환 (절대값)