정점 커버(Vertex Cover) 문제 — 이진 트리로 최소 정점 커버 구하기

무방향 그래프에서 정점 커버(vertex cover)란 그래프의 모든 간선 (u, v)에 대해 u 또는 v 중 적어도 하나가 반드시 집합에 포함되도록 하는 정점들의 부분집합을 의미합니다.

이 문제는 일반 그래프에서는 NP-난해(NP-hard)하지만, 이진 트리(binary tree) 형태의 그래프라면 동적 계획법을 활용해 매우 효율적으로 해결할 수 있습니다.

문제 접근 방식

이 문제는 두 가지 하위 문제로 나눌 수 있습니다.

1. 루트 노드를 정점 커버에 포함하는 경우
루트가 커버 집합에 속하면 루트와 자식들을 연결하는 모든 간선이 자동으로 커버됩니다. 따라서 왼쪽 서브트리와 오른쪽 서브트리의 최소 정점 커버 크기를 각각 구한 뒤, 루트 자신을 위해 1을 더해주면 됩니다.

2. 루트 노드를 정점 커버에 포함하지 않는 경우
루트를 제외하면 루트에 연결된 모든 간선을 커버하기 위해 루트의 모든 자식 노드를 반드시 커버 집합에 포함해야 합니다. 이후 각 자식의 자식들에 대해 재귀적으로 최소 정점 커버를 구합니다.

두 경우 중 더 작은 값을 선택하면 해당 서브트리의 최소 정점 커버 크기를 얻을 수 있습니다.

입력과 출력

입력:
이진 트리 하나.
출력:
최소 정점 커버의 크기 (예시에서는 3).

알고리즘

vertexCover(root)

이 알고리즘에서는 각 노드가 데이터와 함께 해당 노드를 기준으로 커버되는 정점 수(vCover)를 저장합니다. 이미 계산된 값은 다시 계산하지 않으므로 메모이제이션(memoization) 효과를 얻을 수 있습니다.

입력 − 이진 트리의 루트 노드

출력 − 루트를 포함했을 때의 최소 정점 커버 크기

Begin
    if root is φ, then
        return 0
    if root has no child, then
        return 0
    if vCover(root) ≠ 0, then
        return vCover(root)
    withRoot := 1 + vertexCover(left(root)) + vertexCover(right(root))
    withoutRoot := 0

    if root has left child, then
        withoutRoot := withoutRoot + vertexCover(left(left(root))) + vertexCover(left(right(root)))
    if root has right child, then
        withoutRoot := withoutRoot + vertexCover(right(left(root))) + vertexCover(right(right(root)))
    return vCover(root)
End

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int data;       // 노드 데이터
    int vCover;     // 해당 노드까지의 정점 커버 크기 (메모이제이션용)
    node *left, *right;
};

// 새 노드 생성 함수
node *getNode(int data) {
    node *newNode = new (node);
    newNode->data = data;
    newNode->vCover = 0;   // 정점 커버 값을 0으로 초기화
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;        // 새로 생성된 노드 반환
}

int vertexCover(node *root) {
    if(root == NULL)   // 트리가 비어 있는 경우
        return 0;
    if(root->left == NULL && root->right == NULL)   // 루트에서 연결된 간선이 없는 경우(리프 노드)
        return 0;

    if(root->vCover != 0)   // 이미 정점 커버 값이 계산된 노드라면 그대로 반환
        return root->vCover;

    int sizeWithRoot = 1 + vertexCover(root->left) + vertexCover(root->right);   // 루트를 포함하는 경우
    int sizeWithOutRoot = 0;

    if(root->left != NULL)   // 루트를 제외하고 왼쪽 자식을 포함하는 경우
        sizeWithOutRoot += 1 + vertexCover(root->left->left) + vertexCover(root->left->right);
    if(root->right != NULL)  // 루트를 제외하고 오른쪽 자식을 포함하는 경우
        sizeWithOutRoot += 1 + vertexCover(root->right->left) + vertexCover(root->right->right);

    root->vCover = (sizeWithRoot < sizeWithOutRoot)?sizeWithRoot:sizeWithOutRoot;   // 두 경우 중 최솟값 저장
    return root->vCover;
}

int main() {
    // 정점 커버를 확인할 트리 생성
    node *root = getNode(20);
    root->left = getNode(8); root->right = getNode(22);
    root->left->left = getNode(4); root->left->right = getNode(12);
    root->left->right->left = getNode(10); root->left->right->right = getNode(14);
    root->right->right = getNode(25);
    cout << "Minimal vertex cover: " << vertexCover(root);
}

실행 결과

Minimal vertex cover: 3

복잡도 분석

메모이제이션을 사용하기 때문에 각 노드의 정점 커버 값은 한 번씩만 계산됩니다. 따라서 시간 복잡도는 O(n)(n은 노드 수), 공간 복잡도 역시 노드별 값을 저장하기 위한 O(n)입니다. 일반적인 지수 시간 탐욕적 접근보다 훨씬 효율적이라는 점이 이 방법의 핵심 장점입니다.