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

이번 튜토리얼에서는 서로 인접한(직접 연결된) 두 노드를 동시에 선택할 수 없다는 조건 아래에서 이진 트리 노드 값의 합이 최대가 되는 부분집합을 찾는 알고리즘을 다룹니다.

문제 정의

하나의 이진 트리가 주어졌을 때, 부모-자식 관계처럼 직접 연결된 두 노드를 부분집합에 함께 포함할 수 없다는 제약 조건을 만족하면서 노드 값의 총합이 최대가 되도록 하는 것이 목표입니다. 이 문제는 트리 구조에서의 대표적인 동적 계획법(Dynamic Programming) 응용 사례로 자주 등장합니다.

접근 방식

각 노드를 기준으로 다음 두 가지 경우를 모두 계산하고, 그중 더 큰 값을 결과로 취합니다.

현재 노드를 포함하는 경우(Inclusion): 현재 노드의 값을 더하고, 바로 아래 자식 노드는 건너뛴 뒤 손자 노드들부터 탐색을 이어갑니다.
현재 노드를 제외하는 경우(Exclusion): 현재 노드를 선택하지 않고, 왼쪽 자식과 오른쪽 자식 각각에 대해 구한 최대 합을 더합니다.

재귀 호출 과정에서 같은 노드가 반복해서 계산되는 것을 막기 위해 map을 활용한 메모이제이션(Memoization)을 적용합니다. 이미 계산된 노드의 결과가 존재하면 즉시 반환하여 중복 연산을 제거하며, 덕분에 전체 시간 복잡도는 O(N)으로 유지됩니다.

C++ 예제 코드

#include <bits/stdc++.h>
using namespace std;
// 이진 트리 노드 구조체
class Node {
    public:
    int data;
    Node* left;
    Node* right;
};
Node* newNode(int data){
    Node* node = new Node();
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
int sumOfGrandChildren(Node* node, map<Node*, int>& mp);
int getMaxSum(Node* node);
int getMaxSumUtil(Node* node, map<Node*, int>& mp);
int sumOfGrandChildren(Node* node, map<Node*, int>& mp){
    int sum = 0;
    if (node->left)
        sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
    if (node->right)
        sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
    return sum;
}
// 최대 합 반환
int getMaxSumUtil(Node* node, map<Node*, int>& mp){
    if (node == NULL)
        return 0;
    if (mp.find(node) != mp.end())
        return mp[node];
    int incl = node->data + sumOfGrandChildren(node, mp);
    int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
    mp[node] = max(incl, excl);
    return mp[node];
}
int getMaxSum(Node* node){
    if (node == NULL)
        return 0;
    map<Node*, int> mp;
    return getMaxSumUtil(node, mp);
}
int main(){
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
    return 0;
}

출력 결과

결과 해석

예제 트리는 다음과 같은 구조입니다.

          1
        /   \
       2     3
      /     / \
     1     4   5

여기서 노드 2, 4, 5를 선택하면 인접 규칙을 위반하지 않으면서 합이 2 + 4 + 5 = 11이 됩니다. 마찬가지로 루트(1), 가장 왼쪽 리프(1), 그리고 4와 5를 선택해도 합은 11입니다. 어떤 조합도 이 값을 넘을 수 없으므로 최대 노드 합은 11입니다.