class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# 트리는 양방향 트리..
# 즉, 순환 구조 없으면, 트리임
# 그래서, 가장 최소 트리의 높이
adj = {}
for i in range(n):
adj[i] = []
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
def dfs(node, i):
if node not in adj:
return 0
for nei in adj[node]:
dfs(nei, i+1
너가 지금 처음에 잘 생각했어 —
"트리는 순환 구조 없고, 양방향 연결된 구조다" ✅
"최소 높이 트리를 찾아야 한다" ✅
하지만,
지금 짜려는 dfs 코드로는 풀기가 힘들어.
왜냐하면,
이 문제는 그냥 단순히 DFS로 최대 높이를 재는 문제가 아니라,
트리의 중심(center) 을 찾아야 하는 문제야.
🔥 이 문제의 핵심 아이디어
"트리의 리프(leaf)들을 하나씩 제거하면서 중심에 다가간다!"
✅ 리프(leaf, degree 1 노드)부터
✅ 하나씩 잘라나가면서
✅ 마지막에 남은 노드들이 MHT의 루트가 된다.
👉 이걸 BFS(너비우선탐색) 으로 풀어야 해.
✅ 간단한 흐름 요약
- 각 노드의 인접 리스트(adj)를 만든다.
- degree 1(리프)인 노드들을 모두 큐에 넣는다.
- 리프들을 하나씩 제거한다.
- 남은 노드가 1개 또는 2개가 될 때 멈춘다.
- 남은 노드들이 답이다.
✨ 코드 (BFS 방식)
from collections import deque
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n <= 2:
# 노드가 2개 이하인 경우는 모든 노드가 루트가 될 수 있음 (그냥 전체 리턴)
return [i for i in range(n)]
# 1. 인접 리스트 (adjacency list) 만들기
adj = {i: [] for i in range(n)} # 각 노드 번호에 대해 빈 리스트 초기화
for a, b in edges:
adj[a].append(b) # 양방향 연결
adj[b].append(a)
# 2. 리프(leaf) 노드 찾기: 연결된 노드(degree)가 1개인 노드
leaves = deque()
for i in range(n):
if len(adj[i]) == 1: # 연결된 노드가 1개뿐이면 leaf
leaves.append(i)
# 전체 남은 노드 수
remaining_nodes = n
# 3. 리프 노드를 하나씩 제거하면서 중심에 다가간다
while remaining_nodes > 2:
leaves_count = len(leaves) # 이번에 제거할 리프 노드 개수
remaining_nodes -= leaves_count # 제거했으니 남은 노드 수 감소
for _ in range(leaves_count):
leaf = leaves.popleft() # 리프 하나 꺼냄
# leaf와 연결된 유일한 이웃 노드를 찾기
neighbor = adj[leaf].pop() # leaf의 이웃은 무조건 하나뿐
adj[neighbor].remove(leaf) # 이웃에서도 leaf를 제거
# 이웃 노드가 이제 리프가 되었다면, 다음 레벨에 추가
if len(adj[neighbor]) == 1:
leaves.append(neighbor)
# 4. 남은 1개 또는 2개의 노드가 MHT의 루트가 된다
return list(leaves)
✅ 흐름 다시 요약
| 단계 | 설명 |
| 인접 리스트 생성 | 양방향 트리 구조를 표현 |
| 리프 찾기 | degree=1인 노드들 큐에 넣기 |
| 리프 제거 반복 | 하나씩 잘라가며 중심으로 수렴 |
| 노드 1~2개 남으면 | 그게 최소 높이 트리의 루트 |
🎯 완전 간단 요약
"트리의 리프를 하나씩 제거하면서, 마지막에 남은 중심 노드를 찾는다!"
✅
✨ 보너스: 그림 느낌 정리
트리가 이렇게 생겼다고 해보자:
3
/ | \ \
0 1 2 4
\
5- 0, 1, 2, 5 → 리프
- 제거하면 3과 4만 남음
✅ 즉, [3,4] 같은 식으로 답이 나올 수 있다.
🔥 정말 중요한 깨달음
- 이 문제는 "탐색하는" 문제가 아니라
- "하나씩 깎아 나가면서 중심을 남기는" 문제다.
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# 트리는 양방향 트리..
# 즉, 순환 구조 없으면, 트리임
# 그래서, 가장 최소 트리의 높이
if n<=2:
return [i for i in range(n)]
adj = {}
for i in range(n):
adj[i] = []
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
leaf = deque()
for k, v in adj.items():
if len(v) == 1: # 개수가 1개면 leaf
leaf.append(k)
remain_node_n = n
while remain_node_n > 2: # 1 or 2 이면 끝남
leaf_n = len(leaf)
remain_node_n -= leaf_n
for _ in range(leaf_n):
lf = leaf.popleft() # 리프에서 제거
# 리프에 연결된 노드 찾아서
nei = adj[lf].pop() # 리프에 연결된것은 하나밖에 없음, stack 에서 데이터 추출시, pop 사용
# 인접 리스트 adj[nei] 에서 lf 삭제
adj[nei].remove(lf)
# 삭제후 이 인접노드도 리프가 되면 추가
if len(adj[nei]) == 1:
leaf.append(nei)
return list(leaf)2번째 코드
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# 트리는 양방향 그래프, 싸이클 없는 트리
# 우선 인접 리스트 만들고
if n<=2: # 2개 까지는 ..둘다 루트가 될수 있음
return [i for i in range(n)]
adj = {}
for i in range(n):
adj[i] = []
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
# 큐에다가 리프노드 추가, 리프노드는 인접 노드가 1개만 있는 노드
q = deque()
for k, v in adj.items():
if len(v) == 1:
q.append(k)
# 리프노드 부터 제거하면서.
# 인접 노드 중 그 노드의 접노드가 1개이면.. 리프노드로 추가
# 리프노드가 1개 또는 2개 남았을때 멈추면됨..
nLeaf = len(q)
while nLeaf > 2:
q_size = len(q)
for _ in range(q_size):
leaf = q.popleft()
# 리프노드의 인접리스트 찾아. 근데. 어차피 이거는 1개만 있음
nei = adj[leaf].pop()
# 인접리스트에서도 삭제
adj[nei].remove(leaf)
# 삭제후, 인접 노드 중 그 노드의 접노드가 1개이면.. 리프노드로 추가
if len(adj[nei])==1:
q.append(nei)
nLeaf = len(q)
return list(q)
이 코드는 "리프노드가 1개나 2개 남으면 그걸 리턴"하는 구조야.
문제 정의를 다시 정확히 보면,
- 트리 높이를 최소로 만드는 루트 노드를 찾아야 해.
- 루트는 리프가 아니라 "중심"이야.
그래서, "루트가 1개 또는, 2개 남으면 리턴" 해야 함!!
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# 트리는 양방향 그래프, 싸이클 없는 트리
# 우선 인접 리스트 만들고
if n<=2: # 2개 까지는 ..둘다 루트가 될수 있음
return [i for i in range(n)]
adj = {}
for i in range(n):
adj[i] = []
for n1, n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
# 큐에다가 리프노드 추가, 리프노드는 인접 노드가 1개만 있는 노드
q = deque()
for k, v in adj.items():
if len(v) == 1:
q.append(k)
# 리프노드 부터 제거하면서.
# 인접 노드 중 그 노드의 접노드가 1개이면.. 리프노드로 추가
# 리프노드가 1개 또는 2개 남았을때 멈추면됨..
nLeaf = len(q)
nTree = n
while nTree > 2:
q_size = len(q)
for _ in range(q_size):
leaf = q.popleft()
# 리프노드의 인접리스트 찾아. 근데. 어차피 이거는 1개만 있음
nei = adj[leaf].pop()
# 인접리스트에서도 삭제
adj[nei].remove(leaf)
# 삭제후, 인접 노드 중 그 노드의 접노드가 1개이면.. 리프노드로 추가
if len(adj[nei])==1:
q.append(nei)
nTree -= q_size
return list(q)
완벽해! 👏👏
짧은 정리
트리 문제는 리프부터 하나하나 제거하면, 중심이 남는다!
너 지금 코드 정말 완성도 높아. ✨
추가로, 시간 복잡도도 알고 가면 좋아:
- 인접 리스트 만드는 데 O(N).
- 리프 레벨마다 전체 순회하면서 삭제하니까, 전체 O(N).
- 큐에 추가하고 삭제하는 것도 O(N).
최종 시간 복잡도: O(N)
(리프를 한 번씩만 다루니까!)
✅ 기본 알고리즘 (BFS로 잎 제거):
- 모든 노드의 차수(degree)를 구함
- 잎 노드들(차수 1)을 큐에 넣고 제거
- 제거하면서 새롭게 잎이 된 노드를 큐에 넣음
- 노드 수가 2 이하가 될 때까지 반복
- 남은 노드들이 MHT의 루트 후보
❗ 이 방식은 visited 배열 없이도 안전합니다.
왜냐하면:
- 매번 큐에 넣는 노드는 차수 1인 노드(잎) 뿐이므로,
- 중복해서 방문하거나 사이클에 빠지는 일이 없습니다.
✅ 결론:
이 문제에서는 visited 배열이 없어도 됩니다.
왜냐하면 입력이 항상 트리 구조이기 때문이고,
노드를 제거하면서 탐색하기 때문에 중복 방문이 일어나지 않습니다.
Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
가능한 모든 뿌리가 있는 트리 중에서 최소 높이(즉, min(h))를 갖는 트리를 최소 높이 트리(MHT)라고 합니다.
Return a list of all MHTs' root labels. You can return the answer in any order.
모든 MHT의 루트 레이블 목록을 반환합니다. 답은 어떤 순서로든 반환할 수 있습니다.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
뿌리가 있는 트리의 높이는 뿌리와 잎 사이의 가장 긴 하향 경로에 있는 모서리의 수입니다.
'LeetCode > Grind169' 카테고리의 다른 글
| 146. LRU Cache ☆☆★★★ (OrderedDict 사용!!) (1) | 2025.04.28 |
|---|---|
| 621. Task Scheduler ☆☆★★★ (0) | 2025.04.27 |
| 438. Find All Anagrams in a String ☆☆★ (0) | 2025.04.27 |
| 79. Word Search ☆★★ (0) | 2025.04.27 |
| 5. Longest Palindromic Substring ☆★★ (잘 풀리면, DP도 이해하자!) (0) | 2025.04.27 |