C++ 동적 계획법으로 이진 트리에서 인접하지 않은 노드의 최대 합 구하기

이 문제에서는 각 노드가 값을 가지는 이진 트리(Binary Tree)가 주어집니다. 우리의 과제는 동적 계획법(Dynamic Programming)을 활용하여 서로 인접(직접 연결)하지 않는 두 노드를 선택하지 않으면서 얻을 수 있는 노드 값의 최대 합을 구하는 프로그램을 작성하는 것입니다.

문제 설명

주어진 이진 트리에서 노드들을 선택하여 합을 최대화해야 하며, 단 선택된 노드들끼리는 부모-자식 관계처럼 직접 연결되어 있어서는 안 됩니다.

예제로 이해하기

입력

출력

24

설명

선택한 노드: 8 + 5 + 9 + 2 = 24

해결 접근 방식

이 문제는 맵(map)을 활용하여 최대 합(maxSum)을 형성하는 노드들의 합을 찾는 방식으로 해결할 수 있습니다. 문제의 조건에 따라 어떤 노드가 선택되면 그 자식 노드들은 함께 선택될 수 없습니다.

따라서 특정 노드를 선택하기 전에, 해당 노드의 자식 서브트리에 속한 노드들이 더 큰 합을 만들 수 있는지 먼저 확인해야 합니다. 즉, 다음 두 가지 경우를 비교합니다:

• 현재 노드를 포함하는 경우: 현재 노드의 값 + 자식 노드를 제외한 손자 노드 이하의 최대 합
• 현재 노드를 제외하는 경우: 왼쪽 자식과 오른쪽 자식 각각에 대한 최대 합의 총합

그런데 같은 부모-자식 서브트리의 합을 여러 번 반복해서 계산하면 계산 오버헤드가 커지게 됩니다. 이를 해결하기 위해 메모이제이션(Memoization)을 사용하여 각 노드까지의 최대 합을 맵에 저장해 두고, 이후 동일한 노드를 다시 계산할 때 저장된 값을 재활용합니다.

구현 예제

다음은 위 해결 방식의 동작을 보여주는 C++ 프로그램입니다.

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

struct node {
    int data;
    struct node *left, *right;
};

struct node* newNode(int data) {
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum);

// 현재 노드를 포함할 때, 손자 노드 이하에서 얻을 수 있는 최대 합 계산
int sumSubTreeNodes(node* node, map<struct node*, int>& nodeSum) {
    int maxSum = 0;
    if (node->left)
        maxSum += findMaxSumBT(node->left->left, nodeSum) +
                  findMaxSumBT(node->left->right, nodeSum);
    if (node->right)
        maxSum += findMaxSumBT(node->right->left, nodeSum) +
                  findMaxSumBT(node->right->right, nodeSum);
    return maxSum;
}

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum) {
    if (node == NULL)
        return 0;
    // 이미 계산된 값이면 메모이제이션된 결과 반환
    if (nodeSum.find(node) != nodeSum.end())
        return nodeSum[node];
    // 현재 노드를 포함하는 경우
    int sumInclCurr = node->data + sumSubTreeNodes(node, nodeSum);
    // 현재 노드를 제외하는 경우
    int sumExclCurr = findMaxSumBT(node->left, nodeSum) +
                      findMaxSumBT(node->right, nodeSum);
    // 둘 중 더 큰 값을 저장 후 반환
    nodeSum[node] = max(sumInclCurr, sumExclCurr);
    return nodeSum[node];
}

int main() {
    node* root = newNode(9);
    root->left = newNode(4);
    root->right = newNode(7);
    root->left->left = newNode(8);
    root->left->right = newNode(5);
    root->right->left = newNode(2);

    map<struct node*, int> nodeSum;
    cout << "인접하지 않는 노드의 최대 합 (동적 계획법): "
         << findMaxSumBT(root, nodeSum);
    return 0;
}

출력 결과

인접하지 않는 노드의 최대 합 (동적 계획법): 24

정리

이 알고리즘은 각 노드에 대해 '선택하는 경우'와 '선택하지 않는 경우'를 재귀적으로 비교하며 최적해를 찾습니다. 메모이제이션 덕분에 중복 계산이 제거되어 시간 복잡도는 O(N), 공간 복잡도 역시 O(N)으로 효율적으로 동작합니다. 이러한 패턴은 '하우스 로버(House Robber)' 유형의 문제와도 유사하여 트리 구조 응용 문제 학습에 매우 유용합니다.