트리의 중심 (Centroid)

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

정의

트리의 중심 (Centroid) 은 정점 v 를 제거했을 때 생기는 모든 connected component 의 크기가 ⌊N/2⌋ 이하가 되는 정점. 모든 트리는 최소 1개, 최대 2개의 중심을 가진다.

문제 상황과 동기

트리 전체를 한 점을 중심으로 “균형있게” 분해해야 할 때:

naive: 임의의 루트로 잡으면 한쪽 서브트리가 O(N) 가 될 수 있음.
centroid: 어떤 서브트리도 N/2 를 넘지 않음. 재귀 깊이 O(log N).

핵심 통찰: 트리를 반복적으로 centroid 로 쪼개면 전체 트리를 log N 층으로 분해 가능. 중심 분해 의 기초.

PS / 실무 위치: 트리 경로 쿼리, 트리 거리 카운팅, 동적 트리 분할, 네트워크 중심점 찾기.

시각화

핵심 아이디어

invariant: centroid v 를 제거하면 모든 서브트리 크기 ≤ ⌊N/2⌋.

증명 스케치:

트리 T 에서 정점 u 의 “무게” w[u] = u 를 루트로 한 서브트리의 크기 (N - 1 - 자기쪽 서브트리들).
루트에서 시작해 “무거운” 쪽 자식으로 내려가다 w[v] ≤ N/2 가 되는 첫 정점이 centroid.
정점이 N 개면 O(N) 시간에 찾음.
트리는 항상 1개 또는 2개의 centroid 보유 (2개면 인접).

알고리즘

find_centroid(u, parent, N):
    subtree_size = 1
    is_centroid = true
    for v in adj[u]:
        if v == parent: continue
        child_size = find_centroid(v, u, N)
        if child_size > N/2:
            is_centroid = false
        subtree_size += child_size
    
    # parent 쪽 서브트리
    if N - subtree_size > N/2:
        is_centroid = false
    
    if is_centroid:
        return u
    else:
        return subtree_size   # 재귀에서 합산용

실전에서는 DFS 한 번으로 모든 서브트리 크기를 계산한 뒤, 조건 체크.

구현

// O(N) 에 트리의 centroid 찾기
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[200005];
int sz[200005];
bool removed[200005];
int N;

int dfs_size(int u, int p) {
  sz[u] = 1;
  for (int v : adj[u]) {
      if (v == p || removed[v]) continue;
      sz[u] += dfs_size(v, u);
  }
  return sz[u];
}

int find_centroid(int u, int p, int tree_size) {
  for (int v : adj[u]) {
      if (v == p || removed[v]) continue;
      if (sz[v] > tree_size / 2)
          return find_centroid(v, u, tree_size);
  }
  return u;
}

int main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  
  int tree_size = dfs_size(1, 0);
  int c = find_centroid(1, 0, tree_size);
  cout << "Centroid: " << c << "\n";
}

# 간결한 centroid 찾기
import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline

N = int(input())
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)

sz = [0] * (N + 1)
removed = [False] * (N + 1)

def dfs_size(u, p):
  sz[u] = 1
  for v in adj[u]:
      if v == p or removed[v]:
          continue
      sz[u] += dfs_size(v, u)
  return sz[u]

def find_centroid(u, p, tree_size):
  for v in adj[u]:
      if v == p or removed[v]:
          continue
      if sz[v] > tree_size // 2:
          return find_centroid(v, u, tree_size)
  return u

tree_size = dfs_size(1, 0)
c = find_centroid(1, 0, tree_size)
print(f"Centroid: {c}")

// Java centroid finder
import java.util.*;
import java.io.*;

public class Main {
  static List<Integer>[] adj;
  static int[] sz;
  static boolean[] removed;
  static int N;
  
  static int dfsSize(int u, int p) {
      sz[u] = 1;
      for (int v : adj[u]) {
          if (v == p || removed[v]) continue;
          sz[u] += dfsSize(v, u);
      }
      return sz[u];
  }
  
  static int findCentroid(int u, int p, int treeSize) {
      for (int v : adj[u]) {
          if (v == p || removed[v]) continue;
          if (sz[v] > treeSize / 2)
              return findCentroid(v, u, treeSize);
      }
      return u;
  }
  
  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 + 1];
      for (int i = 0; i <= N; i++) adj[i] = new ArrayList<>();
      sz = new int[N + 1];
      removed = new boolean[N + 1];
      
      for (int i = 0; i < N - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      
      int treeSize = dfsSize(1, 0);
      int c = findCentroid(1, 0, treeSize);
      System.out.println("Centroid: " + c);
  }
}

stdin

결과

Centroid: 1

복잡도

항목	값
시간 (centroid 1개 찾기)	O(N)
공간	O(N)
재귀 깊이 (분해 시)	O(log N)

성질

1. 유일성 / 개수

모든 트리는 1개 또는 2개의 centroid 를 가짐. 2개인 경우 반드시 인접.

2. 분할 균형성

centroid v 제거 시:

모든 component 크기 ≤ ⌊N/2⌋.
재귀적으로 각 component 에서 centroid 를 찾으면 총 깊이 O(log N).

3. 경로 길이 합 최소화

N 개 정점 트리에서 “한 점에서 모든 점까지 거리 합” 을 최소화하는 점이 centroid (가 아닐 수도 있지만, centroid 는 항상 상위 후보).

변형

Weighted Centroid

간선에 가중치가 있을 때, “무게 합” 기준으로 centroid 찾기. 알고리즘 동일, sz[u] 대신 weight_sum[u].

Dynamic Centroid

간선 추가/삭제에 대응하는 동적 centroid 는 어려움. 실전에서는 재계산하거나 Link/Cut Tree 같은 고급 자료구조 필요.

함정

1. 서브트리 크기 vs 전체 크기

centroid 판정 시 “parent 쪽” 서브트리도 N/2 체크 필요. 자식 방향만 보면 놓칠 수 있음.

2. removed 배열

중심 분해 에서 이미 제거된 정점은 removed[v] = true 로 마킹. DFS 시 skip 필수.

3. 1-indexed vs 0-indexed

트리 입력이 1-indexed 인지 0-indexed 인지 확인. adj 배열 크기 주의.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 4803	트리	-	kokoa-lab
BOJ 1167	트리의 지름	-	kokoa-lab
BOJ 13159	배열 (중심 분해 응용)	-	kokoa-lab

참고

이 글의 용어 (3개)

중심 분해 (Centroid Decomposition)algorithm: 정의 중심 분해 (Centroid Decomposition) 는 트리를 중심 으로 재귀적으로 분할하여 O(log N) 깊이의 분해 트리 를 만드는 기법. 각 레벨에서 트리 크기가…
최소 공통 조상 (Lowest Common Ancestor)algorithm: 정의 최소 공통 조상 (LCA, Lowest Common Ancestor) 는 트리에서 두 노드 u, v 의 공통 조상 중 가장 깊은 (루트에서 가장 먼) 노드. Binary L…
Graph DP: 트리/DAG 위 DPalgorithm: 정의 Graph DP 는 그래프 구조를 이용한 DP. 사이클 없는 그래프 (트리, DAG) 에서 특히 자연스러움. Tree DP 루트 트리에서 자식 서브트리 결과를 조합. Rer…

이 개념을 다룬 위키 페이지 (1)

wiki중심 분해 (Centroid Decomposition)