[LeetCode#310] Minimum Height Trees

 

❒ Description

---

날짜	2024.09.23 (월)
레벨	Medium
제목	Minimum Height Trees
링크	https://leetcode.com/problems/minimum-height-trees/description/
자료구조	그래프
시간복잡도	O(N)

 

 

 

 

 

❒ 문제 분석

---

이 문제는 트리의 리프 노드에서부터 루트로 다가가며 해결해야 한다. 여기서는 차수가 1인 리프노드를 제거

하면서 루트로 다가가야 한다. 가장 낮은  차수를 제거하는 방식은 위상 정렬과 유사한 방식으로 해석할 수 있다.

 

※ 차수(degree) : 각 노드가 가진 서브트리의 갯수

 

 

 

 

❒ Solution

---

1. 리프노드를 제거하는 방법

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    // 예외 처리
    if (n == 1) return List.of(0);

    // 1. 차수관리를 위해 degree 배열 생성
    int[] degrees = new int[n];

    // 2. 그래프를 인접리스트로 표현
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
        // 3. degrees 배열도 같이 update
        degrees[edge[0]]++;
        degrees[edge[1]]++;
    }
    
    // 4. Q생성 후 차수가 1인 노드들 삽입.
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (degrees[i] == 1) q.offer(i);
    } 	
    
    // 5. 노드가 2개 이하로 남을 때 까지 반복
    while (n > 2) {
        // 6. 최초에 삽입된 차수가 1인 리프노드 갯수 빼기 
        int qSize = q.size();
        n -= qSize;
        for (int i = 0; i < size; i++) {
            int node = q.poll();
            for (int k : graph.get(node)) {
                degrees[k]--;
                if (degrees[k] == 1) {
                    q.add(k);
                }
            }
        }
    }
    
    return new ArrayList<>(q);
}

while (n > 2) {
    int qSize = q.size();
    n -= qSize;
    for (int i = 0; i < size; i++) {
        int node = q.poll();
        for (int k : graph.get(node)) {
            degrees[k]--;
            if (degrees[k] == 1) {
                q.add(k);
            }
        }
    }
}

• 양방향 그래프이기 때문에 for문(i)을 순회
• 새로운 리프노드가 생기면(차수가 1이 되면) q에 삽입
• `n -= qSize` : 현재 q에 있는 갯수만큼 노드를 제거

 

2. 재귀를 통한 풀이 (Time Limit Exceeded)

public class V1 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 결과 배열
        List<Integer> result = new ArrayList<>();
        if (n == 1) {
            result.add(0);
            return result;
        }
        // 최소 높이
        int lowest = Integer.MAX_VALUE;
        // edges 배열 to map
        Map<Integer, List<Integer> > graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new LinkedList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        // main logic
        for (int i = 0; i < n; i++) {
            int height = depth(graph, i, -1);
            if (height < lowest) {
                lowest = height;
                result.clear();
                result.add(i);
            } else if (height == lowest) {
                result.add(i);
            }
        }
        return result;
    }

    private int depth(Map<Integer, List<Integer>> graph, int root, int prev) {
        int depth = -1;
        List<Integer> nextNodes = graph.get(root);
        for (Integer nextNode : nextNodes) {
            if (nextNode != prev) {
                depth = Math.max(depth, depth(graph, nextNode, root));
            }
        }
        depth++;
        return depth;
    }
}

위 코드는 Time Limit Exceeded 에러가 발생하는 코드이다.

 

 

 

 

---