Programmers 86971 - 전력망을 둘로 나누기

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

프로그래머스

 

n개의 송전탑이 트리 형태로 연결되어 있다. 여기서 하나의 전선을 끊어서 네트워크를 2개로 분할하려고 한다. 이때 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞춰야 한다.

두 전력망이 가지고 있는 송전탑 개수의 차이(절댓값)를 return하라.

 

트리 형태이기 때문에 모든 노드가 연결이 되어 있다.

브루트포스를 통해 간선을 하나 제거하고 dfs로 탐색을 하면 하나의 그룹의 송전탑의 개수를 구할 수 있고 n개에서 그 개수를 빼면 나머지 송전탑 그룹의 개수가 결정된다.

이 방법을 지워갈 간선을 하나씩 전부 선택해 가며 반복하면서 차이의 최소를 갱신해 가면 답을 구할 수 있을 것이다.

class Solution {
    
    private int[][] graph;
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        initGraph(n, wires);
        for (int[] wire : wires) {
            // 이번 차례 제외할 wire
            disconnectWire(wire);
            int cnt = dfs(1, new boolean[n + 1]);
            answer = Math.min(answer, Math.abs(n - 2 * cnt));
            // 다시 연결
            connectWire(wire);
        }
        return answer;
    }
    
    private int dfs(int v, boolean[] visited) {
        visited[v] = true;
        
        int cnt = 1;
        for (int u = 0; u < visited.length; u++) {
            if (graph[v][u] == 1 && !visited[u]) {
                cnt += dfs(u, visited);
            }
        }
        
        return cnt;
    }
    
    private void initGraph(int n, int[][] wires) {
        graph = new int[n + 1][n + 1];
        
        for (int[] wire : wires) {
            connectWire(wire);
        }
    }
    
    private void disconnectWire(int[] wire) {
        int v = wire[0];
        int u = wire[1];
        graph[v][u] = 0;
        graph[u][v] = 0;
    }
    
    private void connectWire(int[] wire) {
        int v = wire[0];
        int u = wire[1];
        graph[v][u] = 1;
        graph[u][v] = 1;
    }
}