이진 트리에서 가장 큰 독립 집합(Largest Independent Set) 문제 완벽 정리

독립 집합(Independent Set)이란?

독립 집합(Independent Set)은 이진 트리의 노드들 중에서, 집합에 속한 어떤 두 노드 사이에도 간선(연결 관계)이 존재하지 않는 노드들의 부분 집합을 의미합니다.

즉, 주어진 원소들을 이용해 이진 트리를 구성했을 때, 서로 직접 연결되어 있지 않은 노드들만으로 이루어진 가장 큰 부분 집합을 찾는 것이 이 문제의 목표입니다.

입력 및 출력

입력:
이진 트리

출력:
가장 큰 독립 집합의 크기: 5

알고리즘 설계

이 알고리즘에서는 이진 트리를 구성하며, 각 노드는 데이터(data)와 setSize(집합 크기) 두 가지 정보를 저장합니다. setSize를 활용해 이미 계산된 결과를 재사용함으로써 중복 연산을 방지하는 메모이제이션(Memoization) 기법이 적용됩니다.

입력 − 이진 트리의 루트(root) 노드

출력 − 가장 큰 독립 집합의 크기

longSetSize(root)

Begin
   if root = φ, then
      return 0
   if setSize(root) ≠ 0, then
      return setSize(root)  // 이미 계산된 값이면 재사용
   if root has no child, then
      setSize(root) := 1
      return setSize(root)
   setSizeEx := longSetSize(left(root)) + longSetSize(right(root))  // 루트 제외
   setSizeIn := 1  // 루트 포함

   if left child exists, then
      setSizeIn := setSizeIn + longSetSize(left(left(root))) + longSetSize(left(right(root)))

   if right child exists, then
      setSizeIn := setSizeIn + longSetSize(right(left(root))) + longSetSize(right(right(root)))

   if setSizeIn > setSizeEx, then
      setSize(root) := setSizeIn
   else
      setSize(root) := setSizeEx

   return setSize(root)
End

핵심 아이디어

각 노드를 기준으로 두 가지 경우를 비교합니다.

• 현재 노드를 포함하는 경우(setSizeIn): 노드를 독립 집합에 넣으면 그 자식 노드들은 포함할 수 없으므로, 손자 노드 이하의 서브트리에서 최대 독립 집합을 구해 더합니다.
• 현재 노드를 제외하는 경우(setSizeEx): 노드를 제외하면 왼쪽·오른쪽 자식 서브트리에서 각각 자유롭게 최대 독립 집합을 선택할 수 있습니다.

두 값 중 더 큰 값을 해당 노드의 setSize로 저장하고 반환합니다. 이렇게 하면 전체 시간 복잡도를 효율적으로 유지할 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

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

int longSetSize(node *root) {
   if (root == NULL)
      return 0;

   if (root->setSize != 0)  // 이미 계산된 결과라면 재사용
      return root->setSize;

   if (root->left == NULL && root->right == NULL)  // 자식이 없는 리프 노드
      return (root->setSize = 1);

   // 루트를 제외한 경우: 왼쪽 집합 크기 + 오른쪽 집합 크기
   int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
   int setSizeIn = 1;  // 루트 노드를 포함하는 경우

   if (root->left)  // 왼쪽 서브트리가 존재하면 손자 노드까지 탐색
      setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);

   if (root->right)  // 오른쪽 서브트리가 존재하면 손자 노드까지 탐색
      setSizeIn += longSetSize(root->right->left) + longSetSize(root->right->right);

   root->setSize = (setSizeIn > setSizeEx) ? setSizeIn : setSizeEx;

   return root->setSize;
}

struct node* getNode(int data) {  // 주어진 데이터로 새 노드 생성
   node* newNode = new node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   newNode->setSize = 0;

   return newNode;
}

int main() {
   node *root = getNode(20);
   root->left = getNode(8);
   root->left->left = getNode(4);
   root->left->right = getNode(12);
   root->left->right->left = getNode(10);
   root->left->right->right = getNode(14);
   root->right = getNode(22);

   root->right->right = getNode(25);
   cout << "가장 큰 독립 집합의 크기: " << longSetSize(root);
}

실행 결과

가장 큰 독립 집합의 크기 − 5

위 예제 트리에서는 노드 {20, 4, 10, 14, 25}처럼 서로 인접하지 않은 노드들을 선택하여 크기 5의 독립 집합을 얻을 수 있습니다. 이처럼 동적 계획법(DP)과 메모이제이션을 결합하면 이진 트리의 최대 독립 집합 문제를 효율적으로 해결할 수 있습니다.