[파이썬 알고리즘 인터뷰][트리] 최소 높이 트리

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

그래프의 최소 신장 트리가 되는 루트 출력

 

책에서 구현된 코드

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:
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neighbor = graph[leaf].pop()
                graph[neighbor].remove(leaf)

                if len(graph[neighbor]) == 1:
                    new_leaves.append(neighbor)

            leaves = new_leaves

        return leaves

 

기억해야할 기법

• 최소 신장 트리를 구하는 방법
  
  • 가장 균형잡힌 트리의 높이가 가장 최소
  • 그래프상 가장 가운데 있는 노드가 루트일 때 최소 높이를 가짐
  • 리프 노드를 하나씩 제거하여 루트 찾기

 

내가 구현한 코드

# 못풀고 책의 힌트 보고 작성
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        dic = defaultdict(list)

        if not edges:
            return [k for k in range(n)]

        for x, y in edges:
            dic[x].append(y)
            dic[y].append(x)

        leaves = []
        for k in dic:
            if len(dic[k]) == 1:
                leaves.append(k)
        n -= len(leaves)

        while n > 0:
            nw_leaves = []
            for leaf in leaves:
                node = dic[leaf].pop()
                dic[node].remove(leaf)
                if len(dic[node]) == 1:
                    nw_leaves.append(node)
            n -= len(nw_leaves)
            leaves = nw_leaves

        return leaves

• 힌트를 보고 나서야 코드를 작성할 수 있었음 (문제를 접근하지 못함)
• 트리의 특징과 그래프를 이해해야 문제 접근에 대한 폭넓은 시각을 가질 수 있을 듯 하다
• 최소 신장 트리의 루트 찾는 방법 잊지 말기