[LeetCode] 310. Minimum Height Trees (Daily Question)

문제

---

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.

 

루트가 되었을 때 height가 최소가 되는 노드를 찾는 문제이다.

해당 노드는 여러 개 일 수 있다.

 

Example 1:
Input: n = 4,
edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

 

풀이

---

아이디어

잎 노드는 끝단에 있으므로 루트노드가 되면 height가 커질 것이다.

따라서 잎 노드를 계속 제거 해주는데, 이때 노드가 완전히 사라지기 전까지 반복한다.

 

코드

class Solution:
    
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # 한 노드에 대해 연결된 노드들이 담겨있는 딕셔너리
        # ex) {0: [1, 2, 3], 1: [0, 4]}
        conns = {i: set([]) for i in range(n)}
        for edge in edges:
            node1, node2 = edge
            conns[node1].add(node2)
            conns[node2].add(node1)

        # 다음 탐색 대상 노드
        search_nodes = set(conns.keys())

        # 노드가 2개 이하로 남을 때까지 반복
        while len(conns) > 2:
            leaves = []
            # 잎 노드 탐색
            for node in list(search_nodes):
                if len(conns[node]) == 1:
                    leaves.append(node)

            # 잎 노드는 삭제하고, 잎과 연결되었던 노드가 다음 탐색 대상이 됨
            search_nodes = set([])
            for leaf in leaves:
                node1 = list(conns[leaf])[0]
                del conns[leaf]
                conns[node1].remove(leaf)
                search_nodes.add(node1)

        return list(conns.keys())

 

---

 

후기

---

난이도

노드를 삭제한다는 아이디어를 떠올리기 무척 힘들었다.

구현은 쉬운 편이고 예외사항은 딱히 없어서 아이디어만 떠올린다면 무난하게 풀 수 있을 것이다.