[LeetCode 310] Minimum Height Trees (Java)

🚀 문제 분석

• 목표: $n$개의 노드로 이루어진 트리에서, 특정 노드를 루트로 잡았을 때 트리의 높이가 최소가 되는 모든 노드(MHTs)를 찾습니다.
• 핵심: 트리에서 높이가 최소가 되는 노드는 트리의 정중앙에 위치한 노드들입니다. 트리의 중심은 항상 1개 또는 2개만 존재한다는 수학적 특성을 활용합니다.
• 전략: 리프 노드(연결된 간선이 1개인 노드)를 단계적으로 제거하며 중심부로 좁혀 들어가는 바깥쪽부터 깎기(Pruning) 방식을 사용합니다.

💡 해결 전략: 단계적 리프 제거 (Pruning)

1. DFS의 한계: 모든 노드에 대해 DFS로 높이를 구하면 $O(N^2)$이 되어 $N=20,000$인 조건에서 시간 초과가 발생합니다.
2. 리프 노드 추출: 현재 간선이 1개뿐인 모든 노드(리프)를 큐에 담습니다.
3. 중심부 진입:
   • 큐에서 리프를 꺼내 연결된 부모와의 간선을 끊습니다.
   • 간선이 끊기면서 새로 리프가 된 노드(간선이 1개가 된 노드)들을 다음 차례 큐에 넣습니다.
4. 종료 조건: 남은 노드의 수가 2개 이하가 될 때까지 반복합니다. 마지막에 남은 노드들이 바로 최소 높이를 보장하는 루트 노드입니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return List.of(0);

        // 1. 그래프 인접 리스트 초기화
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new HashSet<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // 2. 초기 리프 노드(간선 1개) 찾기
        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() == 1) leaves.add(i);
        }

        // 3. 중심부 2개 이하 노드가 남을 때까지 깎아내기
        while (n > 2) {
            n -= leaves.size();
            Queue<Integer> nextLeaves = new LinkedList<>();
            for (int leaf : leaves) {
                // 리프의 유일한 이웃을 찾아 관계 끊기
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(neighbor).remove(leaf);
                
                // 새로 리프가 된 노드를 다음 큐에 추가
                if (graph.get(neighbor).size() == 1) nextLeaves.add(neighbor);
            }
            leaves = nextLeaves;
        }

        return new ArrayList<>(leaves);
    }
}

🧐 기술적 고찰

• 시간 복잡도: 각 노드와 간선을 한 번씩만 처리하므로 $O(N)$에 해결됩니다. 팀장님이 우려하셨던 $O(N^2)$을 획기적으로 줄인 최적 풀이입니다.
• 수학적 근거: 트리의 지름(가장 긴 경로)에서 중간에 위치한 노드들이 최소 높이를 형성한다는 원리를 '리프 제거'라는 직관적인 방식으로 구현했습니다.
• 자료구조 선택: Set을 사용하여 간선 제거(remove)를 $O(1)$ 근처로 처리하여 성능을 높였습니다.