트리 (Trees)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 3분 · 1,198자/단어 #algorithm #tree #graph #dfs

정의

트리 (Tree) 는 사이클이 없는 연결 그래프 (acyclic connected graph). N 개 정점이면 정확히 N-1 개 간선. 임의의 두 정점 사이에 유일한 경로 존재.

루트 트리 (Rooted Tree): 특정 정점을 루트로 지정하여 부모-자식 관계를 정의. 대부분 PS 에서 트리는 루트 트리.

문제 상황과 동기

그래프 문제 중 “연결 + 사이클 없음” 조건이 있으면 트리. 트리는 다음 특성으로 많은 문제가 O(N) 으로 풀림:

계층 구조: 루트 → 리프 방향 DFS/BFS 로 순회.
부모-자식 관계: 서브트리 단위로 분할 정복.
경로 유일성: 두 정점 사이 거리 = 경로 길이 (유일).

일반 그래프는 사이클 처리 + 방문 체크가 복잡하지만, 트리는 DFS 한 번이면 모든 정점/간선을 정확히 한 번씩 방문.

시각화

핵심 아이디어

트리 정의 (동치 조건)

N 개 정점 그래프에서 다음은 모두 동치:

연결 + 사이클 없음
연결 + 간선 N-1 개
사이클 없음 + 간선 N-1 개
임의의 두 정점 사이 경로가 정확히 하나

루트 설정

무방향 트리에서 루트를 정하면 간선에 방향 (부모 → 자식) 이 생긴다. DFS/BFS 로 한 번 순회하며:

parent[v]: v 의 부모 (루트는 -1)
depth[v]: 루트에서 v 까지 거리
subtree_size[v]: v 를 루트로 하는 서브트리 크기

재귀 구조

트리 문제는 서브트리 단위 분할 정복 이 핵심. f(v) = “v 를 루트로 하는 서브트리의 답” 을 자식들로부터 모아서 계산.

알고리즘

Input: 무방향 트리 (N 정점, N-1 간선), 루트 r

dfs(u, par):
    parent[u] = par
    depth[u] = (par == -1 ? 0 : depth[par] + 1)
    subtree_size[u] = 1
    for each child v of u (v != par):
        dfs(v, u)
        subtree_size[u] += subtree_size[v]

main:
    dfs(r, -1)

구현

// 트리 DFS: parent, depth, subtree size 계산
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100005];
int parent[100005], depth[100005], sz[100005];

void dfs(int u, int p) {
  parent[u] = p;
  depth[u] = (p == -1 ? 0 : depth[p] + 1);
  sz[u] = 1;
  for (int v : adj[u]) {
      if (v == p) continue;
      dfs(v, u);
      sz[u] += sz[v];
  }
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
      int u, v; cin >> u >> v;
      u--; v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  int root = 0;
  dfs(root, -1);
  for (int i = 0; i < n; i++) {
      cout << "v=" << i << " parent=" << parent[i]
           << " depth=" << depth[i]
           << " sz=" << sz[i] << "\n";
  }
}

# 트리 DFS with sys.setrecursionlimit
import sys
sys.setrecursionlimit(200_000)
input = sys.stdin.readline

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  adj[u].append(v)
  adj[v].append(u)

parent = [-1] * n
depth = [0] * n
sz = [0] * n

def dfs(u, p):
  parent[u] = p
  depth[u] = 0 if p == -1 else depth[p] + 1
  sz[u] = 1
  for v in adj[u]:
      if v == p: continue
      dfs(v, u)
      sz[u] += sz[v]

dfs(0, -1)
for i in range(n):
  print(f"v={i} parent={parent[i]} depth={depth[i]} sz={sz[i]}")

// 트리 DFS: ArrayList + 재귀
import java.util.*;
import java.io.*;

public class Main {
  static int n;
  static ArrayList<Integer>[] adj;
  static int[] parent, depth, sz;
  
  static void dfs(int u, int p) {
      parent[u] = p;
      depth[u] = (p == -1 ? 0 : depth[p] + 1);
      sz[u] = 1;
      for (int v : adj[u]) {
          if (v == p) continue;
          dfs(v, u);
          sz[u] += sz[v];
      }
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      n = Integer.parseInt(br.readLine());
      adj = new ArrayList[n];
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      parent = new int[n];
      depth = new int[n];
      sz = new int[n];
      
      for (int i = 0; i < n - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int v = Integer.parseInt(st.nextToken()) - 1;
          adj[u].add(v);
          adj[v].add(u);
      }
      dfs(0, -1);
      for (int i = 0; i < n; i++) {
          System.out.println("v=" + i + " parent=" + parent[i]
                           + " depth=" + depth[i] + " sz=" + sz[i]);
      }
  }
}

stdin

결과

v=0 parent=-1 depth=0 sz=5
v=1 parent=0 depth=1 sz=3
v=2 parent=0 depth=1 sz=1
v=3 parent=1 depth=2 sz=1
v=4 parent=1 depth=2 sz=1

복잡도

항목	값
DFS 순회	O(N) 시간 (정점 + 간선 각 1회)
공간	O(N) (adj list + 배열)
재귀 깊이	O(N) 최악 (일자 트리)

트리는 간선 수가 N-1 로 고정이므로 DFS/BFS 는 항상 O(N).

기본 연산

LCA (Lowest Common Ancestor)

두 정점 u, v 의 최소 공통 조상. naive O(N), binary lifting / HLD 로 O(log N).

트리 지름 (Diameter)

가장 먼 두 정점 사이 거리. DFS 2회로 O(N).

임의 정점에서 가장 먼 정점 u 찾기
u 에서 가장 먼 정점 v 찾기 → dist(u, v) 가 지름

중심 (Centroid)

제거했을 때 남은 서브트리 크기가 모두 N/2 이하인 정점. 항상 존재 (최대 2개).

변형 / 활용

이진 트리 (Binary Tree)

각 정점의 자식이 최대 2개. 완전 이진 트리는 배열로 표현 (heap).

트라이 (Trie)

문자열 집합을 트리로 표현. 각 간선에 문자 레이블.

세그먼트 트리 / 펜윅 트리

배열을 트리로 표현하여 구간 쿼리 O(log N).

HLD (Heavy-Light Decomposition)

트리 경로 쿼리를 세그트리로 O(log^2 N).

함정

1. 무방향 간선 → 부모 체크

트리 입력은 보통 무방향. DFS 에서 v == parent 체크 빼먹으면 무한 재귀.

2. 루트가 0 이 아닐 때

문제에서 루트를 명시하거나 1번 정점이 루트인 경우 많음. 0-indexed / 1-indexed 주의.

3. 재귀 깊이

Python 은 기본 재귀 깊이 1000. sys.setrecursionlimit() 필수. C++ / Java 는 보통 괜찮지만 일자 트리 (N=10^6) 면 스택 오버플로우 가능.

4. 트리 vs 포레스트

연결 보장 안 되면 포레스트 (여러 트리). 각 컴포넌트마다 DFS.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 11725	트리의 부모 찾기	-	kokoa-lab
BOJ 1167	트리의 지름	-	kokoa-lab
BOJ 1991	트리 순회	-	kokoa-lab
BOJ 15681	트리와 쿼리	-	kokoa-lab

참고

이 글의 용어 (5개)

깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
너비 우선 탐색 (BFS)algorithm: 정의 너비 우선 탐색 (Breadth-First Search, BFS) 는 그래프 G=(V, E) 에서 시작 정점 s 로부터 가까운 정점부터 순서대로 방문하는 알고리즘. 큐 (F…
최소 공통 조상 (Lowest Common Ancestor)algorithm: 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…
graphdata-structure: 개요
Graph DP: 트리/DAG 위 DPalgorithm: 정의 Graph DP 는 그래프 구조를 이용한 DP. 사이클 없는 그래프 (트리, DAG) 에서 특히 자연스러움. Tree DP 루트 트리에서 자식 서브트리 결과를 조합. Rer…