트리 DP 개요

트리 구조에서 동적 계획법을 적용하는 방법론인 트리 DP(Tree Dynamic Programming)는 계층적 데이터를 효율적으로 처리하는 핵심 기법이다. 루트에서 시작해 하위 노드로 전파되는 특성을 활용하며, 자식 노드들의 결과를 조합하여 부모 노드의 최적해를 도출하는 방식으로 작동한다.

핵심 원리

트리 DP의 본질은 정보의 상향 전달에 있다. 각 노드가 자신의 하위 트리에 대한 계산 결과를 상위로 전달하고, 이를 바탕으로 더 큰 문제를 해결한다. 이 과정에서 일반적으로 다음 두 가지 순서를 따른다:

• 전처리 단계: 자식 노드들의 상태값을 먼저 계산
• 병합 단계: 계산된 상태들을 조합해 현재 노드의 상태 확정

상태 설계 패턴

트리 DP 문제의 이도는 상태 정의에서 결정된다. 대표적인 상태 설계 방식은 다음과 같다:

기초 예제: 서브트리 노드 수

각 노드를 루트로 하는 서브트리의 전체 노드 개수를 계산하는 기본 코드다. 후위 순회를 활용해 자식 정보를 먼저 수집한 뒤 현재 노드를 처리한다.

vector<int> graph[MAXN];
int subtreeSize[MAXN];

void computeSize(int current, int parent) {
    subtreeSize[current] = 1;  // 자신 포함
    
    for (int neighbor : graph[current]) {
        if (neighbor == parent) continue;
        
        computeSize(neighbor, current);
        subtreeSize[current] += subtreeSize[neighbor];
    }
}

고전 문제 1: 트리의 중심 찾기

특정 노드를 제거했을 때 생성되는 모든 연결 요소 중 최대 크기가 최소가 되는 지점을 찾는 문제. 각 노드에 대해 세 가지 정보를 종합해야 한다: 각 자식 서브트리 크기, 제거 후 남는 상위 트리 크기.

import java.util.*;

public class TreeCentroid {
    static List<Integer>[] adj;
    static int[] sub;
    static int totalNodes;
    static int bestNode = -1;
    static int minMaxComponent = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        totalNodes = sc.nextInt();
        
        adj = new ArrayList[totalNodes + 1];
        for (int i = 1; i <= totalNodes; i++) {
            adj[i] = new ArrayList<>();
        }
        sub = new int[totalNodes + 1];
        
        for (int i = 0; i < totalNodes - 1; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            adj[a].add(b);
            adj[b].add(a);
        }
        
        solve(1, 0);
        System.out.println(bestNode);
    }
    
    static void solve(int u, int p) {
        sub[u] = 1;
        int localMax = 0;
        
        for (int v : adj[u]) {
            if (v == p) continue;
            solve(v, u);
            sub[u] += sub[v];
            localMax = Math.max(localMax, sub[v]);
        }
        
        int remaining = totalNodes - sub[u];
        localMax = Math.max(localMax, remaining);
        
        if (localMax < minMaxComponent) {
            minMaxComponent = localMax;
            bestNode = u;
        }
    }
}

고전 문제 2: 회사 파티 최대 즐거움

상사와 부하가 동시에 참석할 수 없는 제약 하에서 최대 즐거움을 얻는 문제. 각 직원에 대해 참석 여부를 기준으로 두 가지 상태를 정의한다.

import java.util.*;

public class CompanyParty {
    static List<Integer>[] org;
    static int[][] dp;      // [node][attend: 0 or 1]
    static int[] joy;
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        org = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) org[i] = new ArrayList<>();
        
        joy = new int[n + 1];
        for (int i = 1; i <= n; i++) joy[i] = sc.nextInt();
        
        int[] indegree = new int[n + 1];
        for (int i = 1; i < n; i++) {
            int boss = sc.nextInt(), emp = sc.nextInt();
            org[boss].add(emp);
            indegree[emp]++;
        }
        
        int root = 1;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                root = i;
                break;
            }
        }
        
        dp = new int[n + 1][2];
        visited = new boolean[n + 1];
        
        calculate(root);
        
        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }
    
    static void calculate(int u) {
        visited[u] = true;
        dp[u][1] = joy[u];  // u 참석 시 기본값
        
        for (int v : org[u]) {
            if (visited[v]) continue;
            calculate(v);
            
            // u 미참석: 부하들은 자유롭게
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);
            
            // u 참석: 부하들은 불참해야 함
            dp[u][1] += dp[v][0];
        }
    }
}

활용 팁

트리 DP를 구현할 때 주의할 들:

• 루트 선정: 문제 조건에 따라 적절한 루트를 설정해야 하며, 때로는 임의의 노드를 루트로 삼아도 무관하다
• 메모이제이션: 동일한 상태 반복 계산을 막기 위해 방문 여부를 반드시 체크
• 상태 전이 방향: 자식→부모 방향으로만 정보가 흐르는지, 부모→자식 방향도 필요한지 확인
• 재귀 깊이: 노드 수가 많을 경우 스택 오버플로우에 유의하고 반복문 또는 증가식 재귀 고려