[PGS] 전력망을 둘로 나누기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Solution {
    static int[][] arr;
    static boolean[] used;

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        
        //  연결 상태를 저장할 배열 생성
        arr = new int[n + 1][n + 1];
        for (int[] wire : wires) {
            int a = wire[0];
            int b = wire[1];
            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        for (int[] wire : wires) {
            int a = wire[0];
            int b = wire[1];
            // 일단 연결을 해제
            arr[a][b] = 0;
            arr[b][a] = 0;

            // 최솟값 갱신
            answer = Math.min(answer, bfs(n, a));

            // 다시 연결
            arr[a][b] = 1;
            arr[b][a] = 1;
        }

        return answer;
    }

    private int bfs(int n, int start) {
        used = new boolean[n + 1];

        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        int cnt = 1;

        while (!q.isEmpty()) {
            int now = q.poll();
            used[now] = true;

            for (int i = 1; i <= n; i++) {
                if (used[i]) continue;
                if (arr[now][i] == 1) {
                    q.offer(i);
                    cnt++;
                }
            }
        }
        return Math.abs(n - 2 * cnt);
    }
}

📄 해설

접근

• BFS 를 통해 해결하는 문제
• '우선 연결을 끊고 연결을 끊은채로 차이를 구한 다음, 연결을 회복한다' 라는 접근이 필요
• 모든 전선 중 하나의 연결을 끊으면 두 개의 전력망이 생성되고, 각각에 속한 송전탑의 개수를 구하여 둘의 차이의 최솟값을 구한다.
• 개수를 세는 과정에서 BFS 를 사용한다.

과정

• 연결 상태를 나타낼 배열 arr 을 선언하고, wires 에 있는 전선 정보를 사용해 arr 을 초기화한다. (연결되어있으면 1, 연결되어있지 않으면 0)
• wires 를 순회하면서, 전선을 하나씩 끊어본다.
• 연결이 끊긴 상태로, 전선에 속해있던 송전탑 중 하나를 시작점으로 하여 BFS 탐색을 수행한다.
• BFS 탐색으로 새롭게 생겨난 전력망에 속한 송전탑 개수를 센다.
  • 큐에서 송전탑 번호인 now 를 꺼낸다. (초기에는 시작 송전탑의 번호)
  • 방문하지 않았고, 현재 송전탑과 연결된 송전탑이 있으면 개수를 1 증가시키고 해당 송전탑 번호를 큐에 넣는다.
  • 모든 송전탑 방문이 끝났다면, 차이를 계산한다. 이때 차이는 |n - 2 * cnt| 이다.
    • 새로 생긴 송전탑 개수 cnt, 새로 생긴 다른 송전탑 개수 n-cnt
    • 두 송전탑의 차이는 |n - cnt - cnt| => |n - 2 * cnt|
• 위 과정을 반복하며 얻은 개수와 현재 최솟값을 비교하여 최솟값을 갱신한다.
• 모든 전선에 대한 처리가 끝났다면, 그 시점에서의 answer 의 값이 두 전력망의 송전탑 개수 차이의 최솟값이다.