문제

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

코드

class Solution {
    private int n;
    boolean[] visited;
    boolean[][] arr;
    int count;

    public int solution(int n, int[][] wires) {
        this.n = n;
        int answer = n;

        for (int i = 0; i < wires.length; i++) {
            visited = new boolean[n + 1];
            arr = new boolean[n + 1][n + 1];
            for (int k = 0; k < wires.length; k++) {
                if (k == i) continue;

                int a = wires[k][0];
                int b = wires[k][1];

                arr[a][b] = arr[b][a] = true;
            }
            count = 0;
            dfs(1);
            int result = Math.abs(count * 2 - n);

            answer = Math.min(answer, result);
        }

        return answer;
    }

    public void dfs(int start) {
        visited[start] = true;
        count++;

        for (int i = 1; i <= n; i++) {
            if (arr[start][i] && !visited[i]) {
                dfs(i);
            }
        }
    }
}

생각

문제를 보고 30분 정도 정신을 놨다. 어떻게 풀어야할지 생각이 안나가지고.. 노드를 끊는다는 거에 꽂혀서 어떻게 구현해야할지 감을 못잡았는데 딱히 논리적인 생각을 하고있는 것도아니었는데 문뜩 정답같은 논리가 생각이 나서 풀어버렸다

해당 와이어를 빼고 dfs로 크기를 측정 한다면 두개의 트리 크기를 알 수 있을 것이고 둘의 차를 구하면 된다고 생각하고 작업을 했다.
그러다 전체 크기가 주어진 상황에서 굳이 두 트리의 크기를 모두 측정해야 하나 싶어서 생각해보니까 하나를 구한 후 2를 곱해주고 전체에 빼주면 그 절대값이 두 트리의 크기 차이가 되는 것을 알아 챘고 적용했다.

진짜 못풀거라 생각해서 답을 볼까 생각했었는데 신기하게도 답을 찾을 수 있어서 정말 뿌듯하다.