310. Minimum Height Trees ❌

dasd412·2022년 4월 1일

코딩 테스트

목록 보기

25/71

문제 설명

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

정답 코드 (책 참고, 604ms)

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        graph=dict()
        for u,v in edges:
            if u not in graph:
                graph[u]=[]
            if v not in graph:
                graph[v]=[]
            
            graph[u].append(v)
            graph[v].append(u)
        
        
        if n==1:
            return {0}
        
        leaves=[]
        
        for key in graph:
            if len(graph[key])==1:
                leaves.append(key)
        
        while n>2:
            n-=len(leaves)
            
            new_leaves=[]
            
            for leaf in leaves:
                adjacent=graph[leaf].pop()
                graph[adjacent].remove(leaf)
                
                if len(graph[adjacent])==1:
                    new_leaves.append(adjacent)
                    
            leaves=new_leaves
                
        return leaves

다시 풀어보기 (1차)

전체 코드 (시간 초과)

from collections import defaultdict

class Solution:
    
    def get_max_height(self,current,tree,visited)->int:
        
        visited[current]=True
        visited_count=0
        for adj in tree[current]:
            if visited[adj]:
                visited_count+=1

        if visited_count==len(tree[current]):
            return 0
        else:
            height=0
            for adj in tree[current]:
                if not visited[adj]:
                    visited[adj]=True
                    height=max(height,self.get_max_height(adj,tree,visited))
                    
            return height+1
            
            
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        
        tree=defaultdict(list)
        for u,v in edges:
            tree[u].append(v)
            tree[v].append(u)
        
        length_list=[]
        
        for i in range(n):
            visited=[False]*n
            length=self.get_max_height(i,tree,visited)
            length_list.append((length,i))
        
        length_list.sort(key=lambda x:(x[0]))
        
        min_height=length_list[0][0]
        
        answer=[]
        
        for length,node in length_list:
            if length==min_height:
                answer.append(node)
            else:
                break
        
        return answer

풀이 분석

각 노드를 루트로 해서 재귀를 적용하여 각 루트에서 시작한 깊이를 알아낸 후, 그 중에서 제일 작은 깊이를 추려내는 풀이다. 즉, 시간 복잡도는 O(N) * O(재귀) + O(N)인데 n=최대 2 x 10^4이므로 시간 초과가 난다.

정답 코드 (1차, 7531 ms)

from collections import defaultdict

class Solution:
    
                     
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
             
        answer=set([i for i in range(n)])
        
        tree=defaultdict(list)
        
        for u,v in edges:
            tree[u].append(v)
            tree[v].append(u)
        
        
        while n>2:
            leaf_nodes=[]
            
            for node in tree:
                if len(tree[node])==1:
                    leaf_nodes.append(node)
                    answer.remove(node)
            
            n-=len(leaf_nodes)
            
            for leaf in leaf_nodes:
                adjacent=tree[leaf][0]
                tree[adjacent].remove(leaf)
                del tree[leaf]
            
        return list(answer)

해설 (무게 중심으로 이해하기)

책에 있던 해설을 보니, 최소 높이를 구성하려면 가장 가운데에 있는 값이 루트여야 한다라는 구절이 있었다. 이에 따라 단계적으로 리프 노드를 제거하면 된다. 하지만, 선뜻 이해가 가지 않았다.
그러다가 leetcode best solution을 보고 직관적으로 이해가 갔다.

핵심 아이디어는 다음과 같다.

트리를 하나의 원 영역이라고 본다면, 
리프 노드는 원의 주변 영역 (또는 제일 바깥 영역)이라 할 수 있고
루트 노드는 원의 무게 중심이라고 이해할 수 있다.

즉, 원의 무게 중심에 해당하는 노드를 루트로 한다면, 최소 높이 트리를 구성할 수 있다는 것이다.

예를 들어, 다음 그림을 보자.

맨 왼쪽을 루트로 한다면 원은 어떻게 될까? 중앙에 있는 노드 쪽(무게 중심인 부분)을 루트로 한 원보다 반지름이 크게 될 것이다.
따라서 무게 중심인 부분을 루트로 해야 원으로 커버 해야하는 반지름(또는 길이)이 작아지게 되고, 이는 트리의 최대 높이가 제일 작아지게 되는 것과 같다.