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

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

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

출처 : 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

힌트를 보고 나서야 코드를 작성할 수 있었음 (문제를 접근하지 못함)

트리의 특징과 그래프를 이해해야 문제 접근에 대한 폭넓은 시각을 가질 수 있을 듯 하다

최소 신장 트리의 루트 찾는 방법 잊지 말기

from http://pythaac.tistory.com/119 by ccl(A) rewrite - 2021-08-04 01:00:48