[LeetCode] 310. Minimum Height Trees (Python)

• Reference

Solution

import collections
from typing import List


class Solution:
    # 외곽 노드 -> 한 개의 이웃만 가지는 노드, 트리의 높이를 최소화하는 노드들 중 하나일 수 있음
    # BFS로 탐색 -> 시작 노드부터 시작하여 인접한 노드를 큐에 추가하고, 큐에서 노드를 하나씩 꺼내어 탐색
    # 최소 높이 탐색 방법 -> 외곽 노드로부터 진행하면서 노드들을 탐색, 모든 외곽 노드가 큐에서 제거될 때까지 반복
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # 그래프에 노드가 하나만 있는 경우
        if n == 1:
            return [0]

        graph = collections.defaultdict(set)

        # 인접 리스트(graph) 생성
        for x, y in edges:
            graph[x].add(y)
            graph[y].add(x)

        # 외곽 노드(outsides) 구하기
        outsides = []
        for node in graph:
            if len(graph[node]) == 1:
                outsides.append(node)

        while n > 2:  # 노드가 2 이하가 될 때 중단
            # 현재 외곽 노드의 수를 빼줌으로써 노드의 수 업데이트
            n -= len(outsides)

            # 다음 단계의 외곽 노드를 담는 리스트
            new_outsides = []

            for outside in outsides:
                # 현재 외곽 노드의 이웃 노드
                # pop(): 이웃 노드 중 하나를 선택 후 -> 그 노드를 이외의 이웃들과의 연결을 끊음
                outside_neighbor = graph[outside].pop()

                # 이웃 노드와의 연결을 끊어줌 -> 이를 통해 외곽 노드와 연결된 게 제거됨
                graph[outside_neighbor].remove(outside)

                # 외곽 노드인 경우
                if len(graph[outside_neighbor]) == 1:
                    # 다음 단계의 외곽 노드에 담음
                    new_outsides.append(outside_neighbor)

                outsides = new_outsides

        return outsides