가지를 따라 내려가자냥! 트리 기초
안녕, 나 코딩냥이다냥! 오늘은 트리라냥. 10장에서 그래프를 배웠는데, 트리는 그중에서도 사이클이 없고 하나로 이어진 특별한 그래프라냥.
가계도, 폴더 구조, 회사 조직도가 전부 트리라냥. 오늘은 트리를 훑으며 부모·깊이·크기를 구하는 법을 배운다냥.
오늘의 학습 목표
- 트리가 무엇인지, 어떻게 담는지 안다.
- 루트를 정하고 부모와 깊이를 구한다.
- 서브트리 크기를 후위 순회로 구한다.
- 이진 트리의 세 가지 순회를 안다.
- 트리의 지름을 두 번의 BFS 로 구한다.
1단계 · 트리가 뭐냥 (8분)
트리는 점 n개가 간선 n-1개로 하나로 이어진 그래프라냥. 사이클이
없다냥. 그래서 두 점 사이의 길이 딱 하나뿐이라냥.
비유로 이해하기 — 가계도
맨 위에 시조 할아버지(루트)가 있고, 아래로 자식이 갈라진다냥. 누구든 부모는 하나뿐이라냥. 위로 거슬러 올라가면 반드시 루트에 닿는다냥.
트리에서 "부모가 하나", "사이클이 없다", "n-1개 간선" 은 전부 같은 말이라냥.
담는 법은 10장의 그래프와 똑같다냥. 인접 리스트라냥.
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u) # 방향이 없으니 양쪽 다 넣는다냥간선은 양방향으로 넣어야 한다냥.
트리의 간선에는 원래 방향이 없다냥. u v 가 들어오면 adj[u] 와 adj[v]
둘 다 넣어야 한다냥. 한쪽만 넣으면 트리를 반쪽밖에 못 훑는다냥.
오늘 1번 문제가 이걸 잡는다냥.
2단계 · 루트를 정하고 부모·깊이 (12분)
간선만 주어지면 아직 "위아래"가 없다냥. 루트를 하나 정하면 그때부터 부모와 자식이 생긴다냥. 보통 1번 노드를 루트로 삼는다냥.
루트에서 BFS로 퍼져나가며, 처음 도착하는 쪽을 자식으로 삼는다냥.
from collections import deque
parent = [0] * (n + 1)
depth = [-1] * (n + 1)
depth[1] = 0
q = deque([1])
while q:
u = q.popleft()
for v in adj[u]:
if depth[v] == -1: # 안 간 쪽이 자식이라냥
depth[v] = depth[u] + 1
parent[v] = u
q.append(v)BFS 로 퍼지면, u 에서 v 로 처음 갈 때 u 가 v 의 부모라냥. 이미
방문한 쪽은 u 의 부모니까 건너뛴다냥.
깊이도 같이 적으면 된다냥. depth[v] = depth[u] + 1 이라냥.
부모 찾기와 깊이 구하기는 같은 코드라냥.
오늘 1번(부모)과 2번(깊이) 문제는 입력이 완전히 똑같다냥. BFS 로 훑는 것도 똑같고, 훑으면서 무엇을 적느냐만 다르다냥. 부모를 적으면 1번, 깊이를 적으면 2번이라냥.
트리 문제는 대개 이렇게 "한 번 훑으며 원하는 걸 적는" 모양이라냥.
3단계 · 서브트리 크기 (13분)
각 노드를 뿌리로 하는 작은 트리(서브트리)에 몇 개의 노드가 있는지 구한다냥. 이건 위에서 못 구하고 아래에서부터 세야 한다냥.
비유로 이해하기 — 부하 직원 수 세기
"내 밑에 몇 명이 있냥?" 을 세려면, 각 부하가 자기 밑에 몇 명인지 먼저 알아야 한다냥. 그걸 다 더하고 자기 자신 1을 더하면 된다냥.
그래서 자식을 먼저 다 세고 나를 세는 순서라냥. 이걸 후위 순회라고 한다냥.
size = [1] * (n + 1) # 자기 자신 1로 시작한다냥
def dfs(u, parent):
for v in adj[u]:
if v != parent: # 부모로 되돌아가지 않는다냥
dfs(v, u) # 자식을 먼저 다 센다냥
size[u] += size[v]
dfs(1, 0)재귀 깊이를 조심하자냥. 10장에서 배운 그거라냥.
트리가 일자로 길게 뻗으면 재귀가 그 길이만큼 쌓인다냥. 파이썬 기본 한도는 1000쯤이라, 깊이 5000짜리 트리에서 터진다냥.
import sys
sys.setrecursionlimit(10 ** 6)이 한 줄이 없으면 정답 코드도 RecursionError 로 터진다냥. 오늘 3번 문제에
일자로 뻗은 트리가 숨어 있어서 이걸 잡는다냥.
dfs(v, u) 처럼 부모를 같이 넘기면 방문 배열 없이도 되돌아가지 않는다냥.
트리는 사이클이 없어서 "부모만 아니면 자식" 이라 이게 통한다냥.
4단계 · 이진 트리 순회 (12분)
자식이 왼쪽·오른쪽 둘뿐인 트리를 이진 트리라냥. 순회하는 방법이 세 가지 있다냥. 나(뿌리)를 언제 방문하느냐로 갈린다냥.
- 전위(preorder) — 뿌리 → 왼쪽 → 오른쪽
- 중위(inorder) — 왼쪽 → 뿌리 → 오른쪽
- 후위(postorder) — 왼쪽 → 오른쪽 → 뿌리
왼쪽을 먼저, 오른쪽을 나중에 보는 건 셋 다 같다냥. 뿌리의 위치만 앞·가운데·뒤로 바뀐다냥.
def go(u):
if u == 0: # 자식이 없으면 멈춘다냥
return
pre.append(u) # 전위: 여기서 나를 본다냥
go(left[u])
ino.append(u) # 중위: 여기서 나를 본다냥
go(right[u])
post.append(u) # 후위: 여기서 나를 본다냥세 순회를 한 함수로 한꺼번에 구할 수 있다냥. 왼쪽으로 내려가기 전에 적으면 전위, 사이에 적으면 중위, 다 하고 적으면 후위라냥.
이진 트리도 한쪽으로만 뻗으면 재귀 깊이가 n 이라, 여기서도
setrecursionlimit 이 필요하다냥. 오늘 4번 문제가 그걸 잡는다냥.
5단계 · 트리의 지름 (10분)
트리에서 가장 먼 두 점 사이의 거리를 지름이라 한다냥. 놀랍게도 BFS 두 번이면 구한다냥.
- 아무 점에서 BFS 해서 가장 먼 점
a를 찾는다 a에서 다시 BFS 해서 가장 먼 거리를 구한다 — 그게 지름이라냥
신기하지만 사실이라냥. 아무 데서나 출발해 가장 먼 점은 반드시 지름의 한 끝이라냥. 그래서 거기서 다시 재면 반대쪽 끝까지가 지름이라냥.
def bfs(start):
dist = [-1] * (n + 1)
dist[start] = 0
q = deque([start])
far = start
while q:
u = q.popleft()
if dist[u] > dist[far]:
far = u
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return far, dist
a, _ = bfs(1)
b, dist = bfs(a)
print(dist[b])BFS 라서 재귀 깊이 걱정이 없다냥. 큰 트리에서 안전하다냥. 후위 순회처럼 재귀가 꼭 필요한 게 아니면, 깊이 문제가 없는 BFS 를 쓰는 것도 방법이라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개라냥. 1번 부모, 2번 깊이(1번과 같은 입력이라냥), 3번 서브트리 크기, 4번 이진 트리 순회, 5번 지름이라냥.
1번과 2번을 나란히 풀면 "같은 훑기, 다른 기록" 이 손에 잡힌다냥. 3번과 4번에서는 재귀 깊이를 꼭 챙기자냥. 가보자냥~