1. 문제에 대하여 📦

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

(1) 조건 분석 📊

하나의 연결된 트리가 나온다.
해당 트리의 간선 중 하나를 끊었을 때, 트리가 2분할될텐데, 해당 2분할된 트리간의 정점 차이를 최소화 하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 완전탐색, bfs

간선의 최대 개수가 99개라서, 하나씩 끊어보면서 해도 될 거 같아, 완전 탐색을 활용했다.

다음과 같이 진행된다.

인접 리스트 만들기 (양방향 그래프여야함 주의)
순회하면서 지울 간선을 하나 선택하기
해당 간선을 지우고, 나눠진 왼쪽과 오른쪽에 대해서 BFS를 돌며 각각이 보유한 정점 개수 세기
정점 개수 간의 차를 구해서 차이 최소값 갱신

(1) 시간복잡도 분석 ⏳

정점의 개수 : n 개
간선의 개수 : n-1개

간선 하나마다 n개의 정점에 대한 BFS 반복.
따라서 $O( (n-1) \times (n + n-1))$

3. 코드 🌐

(1) SUDO CODE 💬

0. 인접 리스트 만들기 (양방향 그래프여야함 주의) 
1. 순회하면서 지울 간선을 하나 선택하기
2. 해당 간선을 지우고, 나눠진 왼쪽과 오른쪽에 대해서 BFS를 돌며 각각이 보유한 정점 개수 세기
3. 정점 개수 간의 차를 구해서 차이 최소값 갱신

(2) JAVA CODE ☕

import java.util.*;

class Solution {
    static ArrayList<Integer> [] lists;

    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        lists = new ArrayList [n + 1];

        for(int i = 1; i < n+1; i++){
            lists[i] = new ArrayList<>();
        }

        for(int i = 0; i < wires.length; i++){
            int left = wires[i][0];
            int right = wires[i][1];

            lists[left].add(right);
            lists[right].add(left);
        }


        for(int i = 0; i < wires.length; i++){
            int left = wires[i][0];
            int right = wires[i][1];

            lists[left].remove(Integer.valueOf(right));
            lists[right].remove(Integer.valueOf(left));

            int left_cnt = bfs(left, n);
            int right_cnt = bfs(right, n);

            answer = Math.min(answer, Math.abs(left_cnt - right_cnt));

            lists[left].add(right);
            lists[right].add(left);
        }
        return answer;
    }

    public int bfs(int start, int n) {
        int answer = 0;
        boolean [] isVisited = new boolean [n+1];
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();
        isVisited[start] = true;
        aq1.add(start); 

        while(!aq1.isEmpty()){
            int now = aq1.poll();
            for(int i = 0; i < lists[now].size(); i++){
                int next = lists[now].get(i);
                if(isVisited[next]) continue;
                answer++;
                isVisited[next] =true;
                aq1.add(next);
            }
        }

        return answer;
    }
}

4. 트러블 슈팅 or 배운 점📝

(1) 첫 번째 풀이에서의 배운 점

유니온 파인드로 부분집합 별 정점 개수를 구하려고 했는데, 어짜피 2개로 나누어지는 게 확정난 상황에서 오버 스펙 알고리즘인 거 같다.
하나의 트리로만 이루어져 있다는 지문을 못 보고 지나쳐서 문제를 어렵게 풀었다.

(2) list 자료 구조의 remove 사용 시 주의점

list.remove (int index) 와 list.remove(Object o) 두 개가 있다. 전자는 인수와 같은 index의 값을 지우는 것이고, 둘째는 인수와 같은 value 값을 지우는 것이다.

위의 풀이에서 list에 저장된 value의 자료구조형 또한 int의 Wrapper형인 Integer인데 이를 간과했다. int 형 value 값을 지우려는 의도 였는데 생각없이 list.remove(int i)를 썼다가 index를 지우는 전자가 써져서 오류가 났다.

만약 Integer형 List에서 Integer형 value를 그대로 지우려면, int형 인수를 Integer로 Wrapping 시켜줘서 두 번째 함수가 사용되도록 유도하자.