Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 이진 트리 카메라 배치 문제: 최소 카메라 개수 구하기

문제 개요

이진 트리가 하나 주어지고, 우리는 트리의 노드들에 카메라를 설치하려고 합니다. 특정 노드에 설치된 카메라는 자기 자신, 부모 노드, 그리고 직계 자식 노드를 감시할 수 있습니다. 이때 트리의 모든 노드를 감시하기 위해 필요한 최소 카메라 개수를 구하는 것이 목표입니다.

예를 들어 입력이 다음과 같다면 −

C++로 풀어보는 이진 트리 카메라 배치 문제: 최소 카메라 개수 구하기

출력은 1이 됩니다. 카메라 한 대만으로도 트리의 모든 노드를 감시할 수 있기 때문입니다.

해결 접근 방법: 그리디 + 후위 순회

이 문제는 그리디(Greedy) 전략과 후위 순회(Post-order Traversal)를 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

카메라를 리프(leaf) 노드에 설치하는 것보다 리프의 부모 노드에 설치하는 것이 항상 더 유리합니다. 부모에 카메라를 두면 자기 자신과 두 자식을 동시에 커버할 수 있기 때문입니다. 따라서 트리를 아래에서 위로(후위 순회) 탐색하면서, 자식 중 커버되지 않은 노드가 있으면 현재 노드에 카메라를 설치하는 방식으로 진행합니다.

알고리즘 단계

  1. TreeNode 타입의 집합(set) covered를 정의합니다. (TreeNode는 left, right, val 필드를 가집니다)
  2. solve(node, parent) 함수를 정의합니다.
  3. node가 NULL이면 그대로 반환합니다.
  4. solve(node->left, node)와 solve(node->right, node)를 재귀 호출하여 자식부터 처리합니다.
  5. 다음 조건 중 하나라도 만족하면 현재 노드에 카메라를 설치합니다:
    • 부모가 NULL인데(루트 노드) 자신이 아직 커버되지 않은 경우
    • 왼쪽 자식이 커버되지 않은 경우
    • 오른쪽 자식이 커버되지 않은 경우
  6. 카메라를 설치하면 답(ans)을 1 증가시키고, 현재 노드와 왼쪽 자식, 오른쪽 자식, 부모 노드를 covered에 추가합니다.

메인 메서드 처리 흐름

  • ans := 0으로 초기화합니다.
  • covered에 NULL을 미리 삽입합니다. (NULL 자식은 이미 커버된 것으로 간주하기 위함입니다)
  • solve(root, NULL)을 호출합니다.
  • ans를 반환합니다.

구현 예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
class Solution {
    public:
    set<TreeNode*> covered;
    int ans;
    int minCameraCover(TreeNode* root){
        covered.clear();
        ans = 0;
        covered.insert(NULL);
        solve(root, NULL);
        return ans;
    }
    void solve(TreeNode* node, TreeNode* parent){
        if (!node)
        return;
        solve(node->left, node);
        solve(node->right, node);
        if ((parent == NULL && covered.find(node) == covered.end())
        || covered.find(node->left) == covered.end() || covered.find(node-
        >right) == covered.end()) {
            ans++;
            covered.insert(node);
            covered.insert(node->left);
            covered.insert(node->right);
            covered.insert(parent);
        }
    }
};
main(){
    Solution ob;
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->left->left = new TreeNode(1); root->left->right = new
    TreeNode(1);
    cout << (ob.minCameraCover(root));
}

입력

[1,1,NULL,1,1]

출력

1

복잡도 분석

모든 노드를 한 번씩 방문하므로 시간 복잡도는 노드 수를 N이라 할 때 O(N log N)입니다(집합 연산에 로그 계수가 추가됩니다). 공간 복잡도는 재귀 호출 스택과 covered 집합 때문에 O(N)입니다. 만약 상태 값을 반환하는 방식으로 최적화하면 O(N) 시간에 해결할 수도 있습니다.