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

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

트리 형태의 전력망이 존재할 때, 무작위 전선(간선)을 하나 끊어서 분리된 A,B 송전탑(노드)집합의 개수 차이를 최소화 하는 문제다.

 

핵심 로직은 차이를 구하기 위해 A, B의 개수를 각각 구할 필요가 없다는 것이었다. 다음 식과 같다.
B = 전체 - A
차이 = | A - B |  
즉, 차이 = | A - (전체 - A) |

이후 bfs로 전력망을 하나씩 끊어가며 최소인 경우를 찾았다.
다른 풀이를 찾아보았는데, A의 인접 간선을 하나씩 끊고, 다 끊었으면 인접 노드 B를 추가하여 또 다시 B의 인접 간선을 끊는 방식(dfs)이었다.

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {

        int ans = n;
        boolean[][] adj = new boolean[n][n];

        for(int[] wire : wires) {
            int from = wire[0]-1;
            int to = wire[1]-1;

            adj[from][to] = adj[to][from] = true;
        }

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(adj[i][j]) {

                    int A = 0;

                    // 전력망을 끊음
                    adj[i][j] = adj[j][i] = false;

                    boolean[] visited = new boolean[n];
                    Queue<Integer> q = new ArrayDeque<>();
                    visited[i] = true;
                    q.offer(i);

                    // bfs로 A 전력망 탐색
                    while(!q.isEmpty()) {
                        int e = q.poll();
                        A++;

                        for(int k=0; k<n; k++) {
                            if(!visited[k] && adj[e][k]) {
                                visited[k] = true;
                                q.offer(k);
                            }
                        }
                    }

                    // B = 전체 - A, 차이 = 절댓 값(A-B)
                    ans = Math.min(ans, Math.abs(A - (n - A)));

                    // 전력망 다시 연결
                    adj[i][j] = adj[j][i] = true;
                }
            }
        }

        return ans;
    }
}