핵심 요약
- 백준 2533번(사회망 서비스)은 트리의 ‘최소 정점 피복(Vertex Cover)’ 문제로, 그리디나 레벨(Depth)별 접근이 아닌 트리 DP(Tree DP)로 해결해야 하는 대표적인 문제입니다.
- Tree DP의 본질: 선형 배열이 아닌 계층적 구조에서, “부모의 상태가 자식의 선택지를 제약한다”는 인과관계를 점화식으로 표현하는 기법입니다.
- 상태 정의의 정석:
dp[node][state]를 통해 해당 노드가 얼리어답터인 경우와 아닌 경우를 각각 계산하고, 이를 후위 순회(Post-order)를 통해 부모에게 전달합니다. - 필승 공식(The Formula): DFS를 활용한 1. 방문(Visit) → 2. 위임(Recursive Call) → 3. 결정(Decision)의 3단계 구현 패턴을 제시합니다.
목차
- 1. 서론: 왜 트리에서는 ‘레벨’이 무의미한가?
- 2. [Deep Dive] 부모와 자식의 게임 이론 (점화식 유도)
- 3. [Core Pattern] Tree DP의 절대 공식: 3단계 구현법
- 4. 최종 구현 및 코드 분석
- 5. [Advanced] 시간 복잡도와 스택 오버플로우 방어
- 6. 결론: 분할 정복의 또 다른 이름
1. 서론: 왜 트리에서는 ‘레벨’이 무의미한가?
많은 입문자가 트리 문제를 접할 때, 습관적으로 BFS를 사용하여 ‘레벨(Depth)’별로 묶어서 생각하곤 합니다. “짝수 층이 얼리어답터면 홀수 층은 아니어도 되지 않을까?”라는 직관 때문입니다. 하지만 백준 2533번 문제에서 이 접근은 완전히 실패합니다.
트리는 선형적인 구조가 아닙니다. 어떤 노드는 자식이 100명일 수도 있고(얼리어답터가 되어야 이득), 같은 레벨의 다른 노드는 자식이 없을 수도 있습니다(얼리어답터가 될 필요 없음). 즉, “모든 노드는 각자의 사정(Subtree 구조)이 다르다”는 것을 인정해야 합니다. 따라서 우리는 전체 층을 묶는 것이 아니라, 각 노드별로 독립적인 상태를 정의하고 최적해를 구하는 Tree DP를 도입해야 합니다.
2. [Deep Dive] 부모와 자식의 게임 이론 (점화식 유도)
Tree DP의 핵심은 “나의 선택이 자식에게 어떤 강제력을 행사하는가?”를 정의하는 것입니다. 이 문제에서 연결된 두 노드 사이에는 얼리어답터가 적어도 한 명 있어야 합니다. 이를 나(Parent)를 기준으로 해석하면 다음과 같습니다.
상황 1: 내가 얼리어답터가 아니라면? (dp[me][0])
내가 친구들의 소식을 전해줄 능력이 없습니다. 따라서, 내 친구(자식)들은 선택의 여지 없이 무조건 얼리어답터여야 합니다.
dp[me][0] = ∑ dp[child][1]상황 2: 내가 얼리어답터라면? (dp[me][1])
내가 이미 능력을 갖췄습니다. 내 자식들은 얼리어답터여도 되고, 아니어도 됩니다. 자식들은 각자의 서브트리에서 더 비용이 적게 드는(최적의) 선택을 하면 됩니다.
dp[me][1] = 1 (나 자신) + ∑ min(dp[child][0], dp[child][1])이 두 가지 논리적 귀결이 바로 Tree DP의 점화식이 됩니다.
3. [Core Pattern] Tree DP의 절대 공식: 3단계 구현법
Tree DP는 코드를 작성하는 순서가 매우 중요합니다. 재귀 함수(DFS)의 특성을 이용한 3단계 공식을 반드시 기억하십시오.
Step 1: 방문 및 초기화 (Visit & Init)
현재 노드 cur에 들어왔을 때, dp[cur][0]=0, dp[cur][1]=1 처럼 기저 사례(Base Case)를 설정합니다.
Step 2: 위임 (Delegation / Recursive Call)
자식 노드들을 향해 dfs(next)를 호출합니다. 중요한 점은 이 호출이 끝나고 돌아올 때까지 기다린다는 점입니다. 이것이 바로 후위 순회(Post-order)이며, 자식들이 계산해온 최적해를 받아올 준비를 하는 과정입니다.
Step 3: 결정 (Decision / State Transition)
자식들의 dfs가 끝나면(리턴되면), 자식들의 dp 값을 이용해 나의 dp 값을 갱신합니다. 위에서 유도한 점화식을 이때 적용합니다.
4. 최종 구현 및 코드 분석
위의 공식을 적용한 Java 코드입니다. 입력 크기가 100만 단위이므로 BufferedReader와 ArrayList를 필수적으로 사용해야 합니다.
import java.io.*;
import java.util.*;
public class Main {
static int n;
static List<Integer>[] adj;
static int[][] dp; // [노드번호][0:일반인, 1:얼리어답터]
static boolean[] visited;
public static void main(String[] args) throws IOException {
// 1. 빠른 입출력 설정
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
// 2. 인접 리스트 초기화 (N이 크므로 2차원 배열 불가)
adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
// 3. 트리 구성 (무방향 간선 입력)
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);
}
dp = new int[n + 1][2];
visited = new boolean[n + 1];
// 4. Tree DP 시작 (루트는 임의로 1번으로 지정)
dfs(1);
// 5. 정답 출력: 루트가 얼리어답터일 때와 아닐 때 중 최솟값
System.out.println(Math.min(dp[1][0], dp[1][1]));
}
static void dfs(int cur) {
visited[cur] = true;
// [Step 1] 초기화: 내가 얼리어답터라면 최소 1명(나) 필요
dp[cur][0] = 0;
dp[cur][1] = 1;
for (int next : adj[cur]) {
if (!visited[next]) { // 방문하지 않은 인접 노드 == 자식 노드
// [Step 2] 위임: 자식의 문제를 먼저 해결하고 오라고 명령 (Post-order)
dfs(next);
// [Step 3] 결정: 자식이 가져온 답으로 내 상태 갱신
// 내가 얼리어답터가 아니면(0) -> 자식은 무조건 얼리어답터(1)여야 함
dp[cur][0] += dp[next][1];
// 내가 얼리어답터면(1) -> 자식은 일반인(0)이든 얼리어답터(1)든 상관없음 (최솟값 선택)
dp[cur][1] += Math.min(dp[next][0], dp[next][1]);
}
}
}
}
5. [Advanced] 시간 복잡도와 스택 오버플로우 방어
이 알고리즘의 시간 복잡도는 O(N)입니다. DFS를 통해 모든 노드를 정확히 한 번씩 방문하고, 각 노드에서 자식 수만큼 연산을 수행하기 때문입니다. 간선의 개수가 N-1개이므로 전체 연산량은 N에 비례합니다.
주의할 점은 재귀의 깊이입니다. 트리가 한 줄로 늘어진 경우(Skewed Tree), 재귀 깊이가 N(1,000,000)까지 들어가 Stack Overflow가 발생할 수 있습니다. Java에서는 보통 허용되지만, Python 등의 언어에서는 sys.setrecursionlimit 설정이 필수적입니다. 이 문제에서 Tree DP가 강력한 이유는, 한 번 방문한 노드의 결과값을 메모이제이션하여 중복 계산을 완벽하게 제거하기 때문입니다.
6. 결론: 분할 정복의 또 다른 이름
백준 2533번을 통해 배운 Tree DP는 어렵지 않습니다. “내 문제를 풀기 위해 자식의 답이 필요하다”는 분할 정복의 원리를 트리에 적용했을 뿐입니다.
앞으로 트리 위에서 “최소 선택”, “최대 가중치”, “독립 집합” 같은 키워드를 만난다면, 당황하지 말고 ‘나와 자식 사이의 제약 조건’을 찾으세요. 그리고 DFS라는 도구를 이용해 가장 밑바닥(리프 노드)부터 답을 쌓아 올리십시오. 이 공식만 있다면 어떤 트리 문제도 여러분의 논리를 벗어날 수 없습니다.