[C++로 배우는 알고리즘과 자료구조 심화] Day 18: 트리 동적 계획법 (Tree DP)

트리 동적 계획법 (Tree DP)

트리 동적 계획법(Tree DP)은 트리 구조를 가진 문제를 해결하기 위한 효율적인 방법입니다. 이는 주로 트리의 정점이나 간선을 따라 상태를 정의하고, 하위 트리에서의 정보를 이용하여 전체 문제를 해결하는 기법입니다.

문제 예시: 트리의 최대 독립 집합 (Maximum Independent Set of a Tree)

주어진 트리에서 서로 인접하지 않은 정점의 최대 집합을 찾는 문제입니다. 이는 트리 DP를 사용하여 효율적으로 해결할 수 있습니다.

문제 정의

• 주어진 트리의 정점 수 (n)
• 트리의 간선 정보
• 최대 독립 집합의 크기 계산

트리 DP 구현

다음은 C++로 트리의 최대 독립 집합 문제를 해결하는 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>

const int MAX_N = 100005;

// 트리의 인접 리스트
std::vector<int> tree[MAX_N];

// DP 테이블
int dp[MAX_N][2];

// 방문 여부
bool visited[MAX_N];

// 트리 DP 함수
void treeDP(int node) {
    visited[node] = true;
    dp[node][0] = 0;  // node가 독립 집합에 포함되지 않은 경우
    dp[node][1] = 1;  // node가 독립 집합에 포함된 경우

    for (int neighbor : tree[node]) {
        if (!visited[neighbor]) {
            treeDP(neighbor);
            dp[node][0] += std::max(dp[neighbor][0], dp[neighbor][1]);
            dp[node][1] += dp[neighbor][0];
        }
    }
}

int main() {
    int n;
    std::cout << "정점 수를 입력하세요: ";
    std::cin >> n;

    std::cout << "간선 정보를 입력하세요:\n";
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // 방문 여부 초기화
    std::fill(visited, visited + n + 1, false);

    // 트리 DP 시작 (루트 노드는 1로 가정)
    treeDP(1);

    // 최대 독립 집합 크기 계산
    int maxIndependentSetSize = std::max(dp[1][0], dp[1][1]);
    std::cout << "최대 독립 집합 크기: " << maxIndependentSetSize << std::endl;

    return 0;
}

설명

1. 입력:
   • n: 트리의 정점 수
   • 트리의 간선 정보
2. DP 테이블:
   • dp[node][0]는 node가 독립 집합에 포함되지 않은 경우의 최대 독립 집합 크기를 의미합니다.
   • dp[node][1]는 node가 독립 집합에 포함된 경우의 최대 독립 집합 크기를 의미합니다.
3. 트리 DP 함수:
   • treeDP(node)는 DFS를 사용하여 트리를 순회하며, 각 정점에서의 최대 독립 집합 크기를 계산합니다.
   • node가 독립 집합에 포함되지 않은 경우, 자식 노드들이 포함되거나 포함되지 않은 최대 값을 더합니다.
   • node가 독립 집합에 포함된 경우, 자식 노드들이 포함되지 않은 경우의 값을 더합니다.
4. 결과 출력:
   • 루트 노드에서의 최대 독립 집합 크기를 출력합니다.

트리 동적 계획법의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 19: 스테이트 컴프레션 DP(State Compression DP)"에 대해 학습하겠습니다.