[리트코드(LeetCode)] 310 Minimum Height Trees - Python

Minimum Height Trees - LeetCode

 

 

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

 

풀이

시간초과가 나서 풀이에 성공하지 못한 문제.

 

모든 엣지를 루트로 두고 탐색하기엔 비효율적이라고 생각해서 루트가 되면 확실히 높이가 길어질 것 같은 리프노드는 제외시키고 탐색을 하는 방법을 택했다.

 

딕셔너리 구조를 이용해 각 엣지와 연결된 다른 엣지들을 리스트 형태로 저장한다. 이 때, 해당 엣지가 리프노드라면 리스트의 길이가 1이기 때문에 리프노드를 쉽게 걸러낼 수 있었다.

 

그 다음 남은 엣지들을 루트로 두고 dfs탐색을 통해 최대 높이 길이를 구하고, 다른 엣지들과 비교해서 가장 짧은 높이를 가진 엣지들의 값을 리턴하도록 구현했다.

 

from typing import List
import collections
import sys


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

        if len(edges) == 1:
            return edges[0]

        graph = collections.defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        candidates = []
        for edge in graph:
            if len(graph[edge]) == 1:
                continue
            candidates.append(edge)

        if len(candidates) == 1:
            return candidates

        min_height = sys.maxsize + 1
        visited = [False for _ in range(n)]
        result = []

        def dfs(count, root):
            if len(graph[root]) == 1:
                return count

            max_length = count

            for edge in graph[root]:
                if visited[edge]:
                    continue
                visited[edge] = True
                max_length = max(max_length, dfs(count + 1, edge))
                visited[edge] = False

            return max_length

        for root in candidates:
            visited[root] = True
            count = dfs(0, root)

            if count < min_height:
                result = [root]
                min_height = count
            elif count == min_height:
                result.append(root)
            visited[root] = False

        return result

 

앞서 말한대로 이 구현은 시간초과를 발생한다. 여전히 dfs 탐색을 하는 것이 오래 걸리는 것이다.

 

 

책에서 소개하는 풀이 방법은 리프 노드를 한 번만 걸러냈던 내 방법과는 다르게, 마지막에 노드가 남을 때까지 리프노드를 제거해 나간다.

처음에는 리스트 길이가 1인 노드를 제외하는 것으로 시작해 길이가 2, 3,.. 인 경우를 제외하고 마지막에 남는 노드들을 리턴하도록 한다.

 

from typing import List
import collections


class Solution:
    # 책 풀이. 단계별 리프 노드 제거
    # 내 풀이에서는 리프노드만을 걸러낸 뒤 dfs 탐색을 통해 최소 높이를 찾아다녔다.
    # 여기서는 리프 노드를 제거한 트리에서 다시 리프 노드를 걸러내 마지막까지 남아있는 노드들을 답으로 리턴한다.
    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

 

 

가장 연결이 많은 노드가 루트가 되어야 높이가 최소가 된다는 트리의 특성을 잘 알고 있지 못해서 풀지 못했던 것 같다. (역시 기본기 중요!)

 

 

파이썬 알고리즘 인터뷰 - 교보문고