트리 & Union-Find

the.Dev.Cat 2026. 5. 19. 07:37

트리 & Union-Find -- 코딩테스트 스터디 8주차

1. 트리의 정의와 표현

트리란 무엇인가

사이클이 없는 연결 그래프가 트리다. 정점이 V개이면 간선은 정확히 V-1개다. 간선 하나를 더 추가하면 사이클이 생기고, 하나를 제거하면 연결이 끊긴다.

회사 조직도를 떠올리면 이해하기 쉽다. 대표가 루트, 각 팀장이 자식, 팀원이 리프 노드다. 한 팀원이 두 팀장에 동시에 속하는 일은 없다. 그런 경우가 생기면 그것은 이미 트리가 아니다.

용어 정리

용어	설명
루트(Root)	부모가 없는 최상단 노드
부모(Parent)	자신보다 한 단계 위 노드
자식(Child)	자신보다 한 단계 아래 노드
리프(Leaf)	자식이 없는 노드
깊이(Depth)	루트로부터의 거리 (루트 = 0)
높이(Height)	리프까지의 최대 거리

코딩테스트에서의 입력 형태

코딩테스트에서 트리는 보통 간선 목록으로 주어진다. defaultdict(list)로 인접 리스트를 구성하고 양방향으로 연결하는 것이 기본 패턴이다.

import sys
from collections import defaultdict

def build_adjacency(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

n = 7
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (6, 7)]
graph = build_adjacency(n, edges)
print(graph[1])
print(graph[2])

출력:

[2, 3]
[1, 4, 5]

2. 트리 순회

4가지 순회 방식

전위(Pre-order): 현재 노드 → 왼쪽 → 오른쪽
중위(In-order): 왼쪽 → 현재 노드 → 오른쪽
후위(Post-order): 왼쪽 → 오른쪽 → 현재 노드
BFS(Level-order): 레벨 순서대로, deque 사용

다음 트리를 기준으로 각 순회 결과를 비교한다.

순회 방식	결과
전위	[1, 2, 4, 5, 3]
중위	[4, 2, 5, 1, 3]
후위	[4, 5, 2, 3, 1]
BFS	[1, 2, 3, 4, 5]

재귀 구현

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def preorder(node, result):
    if node is None:
        return
    result.append(node.val)
    preorder(node.left, result)
    preorder(node.right, result)

def inorder(node, result):
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.val)
    inorder(node.right, result)

def postorder(node, result):
    if node is None:
        return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)

def bfs_traversal(root):
    result = []
    q = deque([root])
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

pre, ino, post = [], [], []
preorder(root, pre)
inorder(root, ino)
postorder(root, post)

print("전위:", pre)
print("중위:", ino)
print("후위:", post)
print("BFS:", bfs_traversal(root))

출력:

전위: [1, 2, 4, 5, 3]
중위: [4, 2, 5, 1, 3]
후위: [4, 5, 2, 3, 1]
BFS: [1, 2, 3, 4, 5]

반복문 전위 순회

재귀 깊이가 10만 이상이면 RecursionError가 발생한다. sys.setrecursionlimit으로 한도를 올리거나, 스택으로 순회를 직접 구현한다.

import sys
sys.setrecursionlimit(200000)

def preorder_iterative(root):
    if root is None:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

print("반복 전위:", preorder_iterative(root))

출력:

반복 전위: [1, 2, 4, 5, 3]

중위 순회는 이진 탐색 트리(BST)에서 오름차순 정렬 결과를 낸다는 특성이 있어, BST 검증 문제에서 자주 활용된다.

3. LCA (최소 공통 조상)

정의

LCA(Lowest Common Ancestor)는 두 노드의 조상 중 가장 깊은 공통 정점이다.

4와 5의 LCA = 2 (두 노드 모두 2의 자식)
4와 3의 LCA = 1 (2와 3의 공통 조상은 1뿐)

전처리: parent와 depth 배열 구성

루트에서 BFS를 돌며 각 노드의 부모와 깊이를 기록한다.

from collections import deque, defaultdict

def build_tree(n, edges, root):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    visited = [False] * (n + 1)

    q = deque([root])
    visited[root] = True
    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                parent[neighbor] = node
                depth[neighbor] = depth[node] + 1
                q.append(neighbor)

    return parent, depth

Naive LCA

두 노드의 깊이를 같은 수준으로 맞춘 뒤, 같은 노드에 도달할 때까지 동시에 부모 방향으로 올라간다.

def find_lca(parent, depth, u, v):
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]
    while u != v:
        u = parent[u]
        v = parent[v]
    return u

n = 5
edges = [(1, 2), (1, 3), (2, 4), (2, 5)]
parent, depth = build_tree(n, edges, root=1)

print("4와 5의 LCA:", find_lca(parent, depth, 4, 5))
print("4와 3의 LCA:", find_lca(parent, depth, 4, 3))
print("2와 3의 LCA:", find_lca(parent, depth, 2, 3))

출력:

4와 5의 LCA: 2
4와 3의 LCA: 1
2와 3의 LCA: 1

시간복잡도 한계

Naive LCA는 쿼리 한 번에 O(V)가 걸린다. 트리가 한쪽으로 편향되면 최악의 경우 V번 올라가야 한다. 이진 리프팅(sparse table)을 사용하면 전처리 O(V log V), 쿼리 O(log V)로 줄일 수 있다. 이진 리프팅은 이번 주 범위 밖이다.

4. Union-Find (분리 집합)

친구 관계 비유

A와 B가 친구, B와 C가 친구이면 A, B, C는 같은 그룹이다. 이런 "같은 그룹인가?"를 빠르게 판별하는 자료구조가 Union-Find다.

각 원소는 처음에 자기 자신을 루트로 가진다. union으로 두 원소를 같은 그룹으로 합치고, find로 루트를 찾아 같은 그룹인지 판별한다.

기본 구현

def init_parent(n):
    return list(range(n + 1))

def find_naive(parent, x):
    if parent[x] == x:
        return x
    return find_naive(parent, parent[x])

def union_naive(parent, x, y):
    rx = find_naive(parent, x)
    ry = find_naive(parent, y)
    if rx != ry:
        parent[ry] = rx

parent = init_parent(5)
union_naive(parent, 1, 2)
union_naive(parent, 2, 3)

print(find_naive(parent, 1) == find_naive(parent, 3))
print(find_naive(parent, 1) == find_naive(parent, 4))

출력:

True
False

순진 구현의 한계

1 → 2 → 3 → 4 → ... 순서로 union을 반복하면 트리가 한쪽으로 편향된다. 이 경우 find 한 번에 O(V)가 걸린다.

5. 경로 압축과 랭크 최적화

경로 압축

find를 호출할 때, 지나친 모든 노드를 루트에 직접 연결한다. 이후 같은 경로를 다시 탐색할 때 O(1)에 루트를 찾을 수 있다.

압축 전:  x → a → b → root
압축 후:  x → root
          a → root
          b → root

union by rank

랭크가 낮은 트리를 높은 트리 아래에 붙인다. 랭크가 같을 때만 높이가 1 증가한다. 이로써 트리가 불필요하게 깊어지는 것을 막는다.

UnionFind 클래스 전체 구현

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(6)
uf.union(1, 2)
uf.union(2, 3)
uf.union(4, 5)

print(uf.same(1, 3))
print(uf.same(1, 4))
print(uf.same(4, 5))

출력:

True
False
True

재귀 깊이가 우려되면 반복문 find를 사용한다.

def find_iterative(parent, x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root

6. 활용 패턴

사이클 판별

간선을 하나씩 추가할 때, 두 끝점이 이미 같은 집합이면 사이클이 존재한다. 크루스칼 알고리즘에서 이 원리를 사용한다.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if uf.same(u, v):
            return True
        uf.union(u, v)
    return False

edges_no_cycle = [(1, 2), (2, 3), (3, 4)]
edges_with_cycle = [(1, 2), (2, 3), (3, 1)]

print(has_cycle(4, edges_no_cycle))
print(has_cycle(3, edges_with_cycle))

출력:

False
True

그룹(연결 요소) 개수 세기

모든 노드의 루트를 find로 구한 뒤, 서로 다른 루트의 수를 센다.

def count_groups(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return len(set(uf.find(i) for i in range(1, n + 1)))

print(count_groups(5, [(1, 2), (2, 3)]))
print(count_groups(5, [(1, 2), (3, 4)]))

출력:

3
3

MST(최소 신장 트리)를 구하는 크루스칼 알고리즘도 Union-Find를 핵심으로 사용한다. 크루스칼은 이번 주 범위 밖이므로 예고만 남긴다.

7. 시간 복잡도 정리

연산	시간복잡도	비고
트리 순회	O(V)	노드 수
LCA (Naive)	O(V) per query	편향 트리 최악
LCA (sparse table)	O(log V) per query	이진 리프팅
Union-Find (경로압축+랭크)	O(α(V)) ≈ O(1)	역 아커만 함수

8. 연습 문제

문제	난이도	링크	핵심 접근
길 찾기 게임	Lv 3	프로그래머스	x좌표 기반 이진 탐색 트리 구성 후 전위/후위 순회
다단계 칫솔 판매	Lv 3	프로그래머스	부모 배열 따라 수익 전파, 트리 거슬러 올라가기
섬 연결하기	Lv 3	프로그래머스	크루스칼 + Union-Find, 최소 비용 간선 선택
네트워크	Lv 3	프로그래머스	Union-Find로 연결 요소(그룹) 개수 계산