이진 트리에서 인접하지 않는 노드의 최대 합 구하기

이 튜토리얼에서는 동적 프로그래밍(Dynamic Programming)을 활용하여 이진 트리에서 서로 인접하지 않는 노드들의 최대 합을 구하는 프로그램을 다룹니다.

문제 개요

이진 트리가 주어졌을 때, 목표는 부모-자식 관계로 직접 연결된 두 노드를 동시에 선택하지 않는다는 조건 하에서 노드 값의 합이 최대가 되는 부분 집합을 찾는 것입니다.

동적 프로그래밍 접근 방법

핵심 아이디어는 각 노드에 대해 두 가지 상태를 정의하는 것입니다.

dp1[node]: 해당 노드를 선택하는 경우 얻을 수 있는 최대 합
dp2[node]: 해당 노드를 선택하지 않는 경우 얻을 수 있는 최대 합

점화식은 다음과 같이 표현할 수 있습니다.

dp1[node] = tree[node] + Σ dp2[child] → 노드를 선택하면 모든 자식 노드는 선택할 수 없습니다.
dp2[node] = Σ max(dp1[child], dp2[child]) → 노드를 선택하지 않으면 각 자식에 대해 더 큰 값을 자유롭게 취할 수 있습니다.

DFS(깊이 우선 탐색)로 리프 노드부터 위로 올라가며 값을 계산한 뒤, 루트 노드에서 max(dp1[root], dp2[root])가 곧 정답이 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// DFS를 이용한 동적 프로그래밍 계산
void dfs(int node, int parent, int dp1[], int dp2[], list<int>* adj, int tree[]){
    int sum1 = 0, sum2 = 0;
    for (auto i = adj[node].begin(); i != adj[node].end(); ++i) {
        if (*i == parent)
            continue;
        dfs(*i, node, dp1, dp2, adj, tree);
        sum1 += dp2[*i];
        sum2 += max(dp1[*i], dp2[*i]);
    }
    dp1[node] = tree[node] + sum1;
    dp2[node] = sum2;
}

int main() {
    int n = 5;
    list<int>* adj = new list<int>[n + 1];
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    adj[5].push_back(2);

    int tree[n + 1];
    tree[1] = 10;
    tree[2] = 5;
    tree[3] = 11;
    tree[4] = 6;
    tree[5] = 8;

    int dp1[n + 1], dp2[n + 1];
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);

    dfs(1, 1, dp1, dp2, adj, tree);
    cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl;
    return 0;
}

출력 결과

Maximum sum: 25

예제 해설

위 예제의 트리 구조는 다음과 같습니다.

노드 1(값 10)이 루트이며, 노드 2(값 5)와 노드 3(값 11)을 자식으로 가집니다.
노드 2는 노드 4(값 6)와 노드 5(값 8)를 자식으로 가집니다.

루트인 노드 1을 선택하면 자식인 노드 2, 3은 선택할 수 없으므로 10 + 6 + 8 = 24입니다. 반면 노드 3을 선택하면 노드 4와 5는 노드 3과 직접 연결되어 있지 않아 함께 선택할 수 있고, 11 + 6 + 8 = 25가 됩니다. 따라서 최종 답은 25입니다.

시간 및 공간 복잡도