[BFS] 전력망을 둘로 나누기

 

 

1. 위 문제와 같이 노드와 노드가 연결되어있는 문제의 경우,

    인접관계행렬을 만들어 각 노드간 연결되어있을 경우 1, 연결되어있지 않을 경우 0으로 설정해, 배열을 만든다.

 

2. BFS를 이용해, 선을 하나씩 끊고, 복구하기를 반복하면서 " |두 전력망의 송전탑 개수 차| "가 가장 작은값을 반환한다.

 

3. BFS / DFS 모두 각 노드를 방문 했는지 안했는지를 나타내는 boolean[] visited를 생성해야 한다.

 

4. BFS에서는 Queue를 사용하는데, 처음 기준이 되는 노드를 넣어주고,

    이 노드와 연결되어 있는 다음 노드를 추가하고 삭제하는데 사용 된다.

 

코드

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    int[][] arr;
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
 
        // 인접관계 행렬 만들기
        arr = new int[n+1][n+1];
        for(int i=0;i<wires.length;i++){
            arr[wires[i][0]][wires[i][1]] = 1;  //1과3 연결관계 1로 설정
            arr[wires[i][1]][wires[i][0]] = 1;  //3과1 연결관계 1로 설정
        }
        
        // 선 하나씩 끊으면서 bfs 탐색
        for(int i=0;i<wires.length;i++){
            int left = wires[i][0];		// 끊은 전선 기준 왼쪽 송전탑
            int right = wires[i][1];	// 끊은 전선 기준 오른쪽 송전탑
            
            // 선 끊기
            arr[left][right] = 0;
            arr[right][left] = 0;
            
            // bfs
            answer = Math.min(answer, bfs(left,n));		(1)
                
            // 끊었던 선 복구
            arr[left][right] = 1;
            arr[right][left] = 1;
        }
        
        return answer;
    }
    
    public int bfs(int left, int n){
        int cnt = 1;    // 기본으로 자기자신인 송전탑이 있으므로 1부터 시작
        boolean[] visited = new boolean[n+1];
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(left);
        
        while(!queue.isEmpty()){				(2)
            int temp = queue.poll();
            visited[temp] = true;
            for(int i=1;i<n+1;i++){
                if(arr[temp][i] == 1 && !visited[i]){
                    queue.add(i);   // 연결되어있는 다음 노드로 넘어가기 위해 queue에 추가
                    cnt++;          // 연결된 노드 하나 찾았으므로 +1
                }
            }
        }
        
        return Math.abs(cnt-(n-cnt));
    }
}

 

위 코드에서 중요한 부분 2가지에 대해서 더 자세히 살펴보자.

 

(1)

// bfs
answer = Math.min(answer, bfs(left,n));

 

BFS 문제에서는 BFS 메소드에 어떤 인자값을 넘겨줄것인가가 중요하다.

나의경우 처음엔 bfs( left, right, n )을 했었다.

하지만 전체 송전탑 개수인 n이 주어지고, queue에 인접 노드를 넣어가며 탐색하므로 right값을 쓸 일이 없어졌다.

 

왜냐하면, 끊은 전력망을 기준으로 left와 연결된 송전탑 개수를 cnt로 하여 구하면,

right와 연결된 송전탑의 개수는 (n-cnt)로 구할 수 있기 때문이다.

 

따라서, bfs 메소드에 넘길 인자값은 left 와 총 송전탑 개수인 n  두 가지면 충분하다.

 

(2)

 while(!queue.isEmpty()){
            int temp = queue.poll();
            visited[temp] = true;
            for(int i=1;i<n+1;i++){
                if(arr[temp][i] == 1 && !visited[i]){
                    queue.add(i);   // 연결되어있는 다음 노드로 넘어가기 위해 queue에 추가
                    cnt++;          // 연결된 노드 하나 찾았으므로 +1
                }
            }
        }

 

 queue : left를 포함하여 left와 인접해 있는 노드 번호를 가지는 큐.

 arr : 인접 관계를 나타내는 행렬.

 

1. left가 들어있는 queue에서 값을 가져와 left 송전탑의 visted를 true로 설정.

2. left와 인접관계를 가지고 아직 방문하지 않은 송전탑( i )이면 queue에 추가.

3. 큐에 추가 후, 인접 노드가 있으므로 cnt 값을 1 올려줌.

 

 

 

 

 

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