[LeetCode] 310. Minimum Height Trees

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

트리의 모든 노드를 루트로 선택할 수 있습니다. 가장 낮은 높이가 되게 루트를 선택해서 반환하세요.

✍️ 풀이

---

약간의 생각의 전환이 필요한 문제이다.
최소 높이를 구하기 위해 루트를 선택하는 것이 아닌 리프 노드 부터 삭제 해나가면 남아있는 노드를 통해 루트 노드를 구할 수 있다.

1. 무방향 그래프이므로 딕셔너리에 양쪽 엣지를 모두 저장한다.
2. 모든 딕셔너리를 돌면서 간선이 하나인 노드를 찾아 리스트에 추가한다. (리프노드들)
3. 찾은 리프노드를 딕셔너리에서 삭제하고 무방향이므로 반대편 노드에서도 노드의 삭제를 진행한다.
4. 삭제를 진행한 반대편 노드의 간선의 갯수가 1이면 이 노드가 다시 리프 노드가 된다.
5. 전체 노드의 갯수가 2보다 같거나 작을 때 까지 진행하며 반복을 진행하고 남은 리프 노드가 루트 노드가 된다.

🛠 코드

---

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]

        # 양방향 그래프 구성
        graph = collections.defaultdict(list)
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)

        # 첫 번째 리프 노드 추가
        leaves = []
        for i in range(n + 1):
            if len(graph[i]) == 1:
                leaves.append(i)

        # 루트 노드만 남을 때까지 반복 제거
        while n > 2:  # 2개 남았을 땐 서로가 리프노드가 되므로 반복문을 빠져나온다.
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neighbor = graph[leaf].pop()  # 1개 연결되있던 노드를 빼서 다음 조건 노드로 선택한다.
                graph[neighbor].remove(leaf)  # 일단 리프노드를 제외시킨다.

                if len(graph[neighbor]) == 1:  # 다음 조건 노드의 값의 갯수가 1인지(리프노드) 검사한다.
                    new_leaves.append(neighbor)

            leaves = new_leaves

        return leaves

---

📝 정리

---

반복을 2보다 클 때까지만 진행하는 이유는 노드가 2개 남았을 때는 서로가 리프노드이므로 더 진행하면 루트노드를 구할 수 없다. 또한 노드가 1개 남았을 때도 더 이상 리프노드도 없고 자신이 바로 루트노드이므로 바로 반환하면 된다.

🎈 참고

---

Book 링크