(H - 968. Binary Tree Cameras) 노드 상태 강제 (제약 추가 전략)

문제 설명이 간단하다고 너무 얕본 것 같다.

몇 가지 방법 생각해서 구현해봤지만, 실패하고 해설봄

 

노드에 카메라를 설치하면, parent와 children을 모두 커버할 수 있다.

트리의 모든 노드를 커버하기 위해 필요한 최소 카메라 수는?

 

 

생각해본 방법

Sol1) root 혹은 root 바로 아래 children에서 출발해서, 한 레벨 색칠하면 다음 레벨은 건너뛰는 식으로 격자로 색칠

→ 두 레벨 연속 건너뛰는 반례가 존재

 

Sol2) Leaf parent만 먼저 색칠한 마음, root에서 내려오면서 아직 커버 못한 노드에 캠 설치 (Greedy)

→ 후자 방법에 반례 존재 (root를 먼저 탐색하면 안되는 경우); 참고로 Leaf에서 올라가는 방식 해도 반례 존재

 

기타 실패한 방법 (반례 존재)

- Connectivity 기준으로 색칠 여부 결정
ex) 카메라 설치했을 때 영향 받는 다른 노드 개수가 N개 이상

→ 단순한 방법인 만큼, 반례 바로 나옴

 

생각나는 방법마다 반례가 생기니, 이쯤되면 깨달을만도 함.

 

단순한 rule-based 색칠은 안 통한다!

 

Tree DP처럼 가능한 모든 경우를 따져주기? 다른 방법?

---

해설 1) Greedy

 

직관적으로, leaf의 parent에 카메라를 설치하는 방법이 맞다고 생각함 (Sol2 에서 활용)

Leaf 노드 수가 더 많고, 그걸 일일히 다 색칠하는 것보다 parent를 칠하는게 더 나은 선택이니까.

 

좀 더 엄밀한 증명?

If we set a camera at the leaf, the camera can cover the leaf and its parent.
If we set a camera at its parent, the camera can cover the leaf, its parent and its sibling.

https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS

> 논리적으로, Leaf에 카메라 설치하는 것보다 Leaf의 parent에 설치하는게 항상 낫다.

 

이 아이디어를 트리 전체에 확장시킬 수 없을까?

 

카메라를 설치한 노드와 그 노드로 인해 커버되는 노드들을 제거하면,
또 새로운 Leaf 노드가 생길테고 위 명제를 사용할 수 있다!

 

 

[구현]

각 노드에 3가지 state를 부여한다 : LEAF, LEAF_PARENT, COVERED

LEAF는 말 그대로 해당 노드가 LEAF일 때,

LEAF_PARENT는 child 중 LEAF가 있어서, 카메라를 새로 설치할 때

COVERED는 child 중 LEAF_PARENT가 있어서 이미 커버된 노드를 표시할 때.

 

LEAF_PARENT나 COVERED를 반환하는게 아니라면 무조건 LEAF를 반환하게 DFS 코드를 짜면 로직 구현 완료.

class Solution {
public:
    int cam_cnt = 0;
    
    // 3 states for each node
    enum state {LEAF, LEAF_PARENT, COVERED};
    
    int DFS(TreeNode* node){
        if(node == nullptr) return COVERED;
                
        int left = DFS(node->left);
        int right = DFS(node->right);

        if(left == LEAF || right == LEAF){
            cam_cnt++;
            return LEAF_PARENT;
        }
        else if(left == LEAF_PARENT || right == LEAF_PARENT)
            return COVERED;
        
        return LEAF;
    }
    
    int minCameraCover(TreeNode* root) {        
        int root_status = DFS(root);        
        return (root_status < 1 ? 1 : 0) + cam_cnt;
    }
};

 

---

해설 2) DP? DFS!

 

각 노드의 상태를 다음 3가지로 제한하자.

 

1. Not-covered

: 현재 노드 커버X, Children은 모두 Covered (카메라X)

→ Parent node에서 반드시 카메라 설치해야 함

 

2. Covered

: 카메라 설치된 Child가 적어도 하나 존재해서, 현재 노드에 카메라 없어도 커버된 상태

 

3. Cam

: 현재 노드에 카메라 설치. Child는 어떤 상태던지 상관X

차례대로 ncov, cov, cam

 

이렇게 상태를 고정시키면, 상태에 따른 노드 간 관계를 정의할 수 있다.

 

해당 노드를 거치는 DFS의 반환값 : 

해당 노드를 root로 할 때, 3가지 각 상태에 필요한 최소 카메라 수

 

(3가지 상태에 따른 카메라 수를 담는 struct 사용해서 깔끔하게 구현)

struct ResultType{
    int ncov; // children covered & current node not covered
    int cov; // at least one child has cam & current node covered
    int cam; // current node cam
    ResultType(int a=0, int b=0, int c=0):ncov(a), cov(b), cam(c){};
    
    friend ostream& operator<< (ostream& os, const ResultType& a);
};

ResultType DFS(TreeNode* node){
	// ...
}

 

임의의 노드에서 살펴보면, 

 

1. ncov가 되기 위해선 L, R 모두 covered여야 함

current.ncov = L.cov + R.cov;

 

2. cov가 되기 위해선, L 혹은 R 혹은 둘다 cam을 가지고 있어야 함

(참고로, 카메라가 없는 child는 uncovered 상태면 안되겠지! 현재 노드에서 카메라를 설치하지 않으니)

 

current.cov = min(L.cam + R.cov, L.cov + R.cam, L.cam + R.cam)

 

3. cam 설치하면 child의 상태는 뭐가 되든 상관 없음

current.cam = 1 + min(가능한 모든 상태)

 

이렇게 매 노드마다 반복됨.

최종적으로 root노드의 cov 값과 cam 값 중 더 작은 값이 답.

 

주의)

- Leaf node는 cov상태가 될 수 없기에, node == nullptr시 반환 값은 (0,0,INF)여야 함

struct ResultType{
    int ncov; // children covered & current node not covered
    int cov; // at least one child has cam & current node covered
    int cam; // current node cam
    ResultType(int a=0, int b=0, int c=0):ncov(a), cov(b), cam(c){};
    
    friend ostream& operator<< (ostream& os, const ResultType& a);
};

ostream& operator<< (ostream& os, const ResultType& a){
    os << a.ncov << " " << a.cov << " " << a.cam << '\n';
    return os;
}

class Solution {
public:
    int cam_cnt = 0;
    
    ResultType DFS(TreeNode* node){
        if(node == nullptr) return ResultType(0,0,1001);
        // 1e9 -> Leaf node cannot have status 'cov'
                
        ResultType L = DFS(node->left);
        ResultType R = DFS(node->right);

        int LcovMin = min(L.cov, L.cam);
        int RcovMin = min(R.cov, R.cam);
        
        ResultType res;
        res.ncov = L.cov + R.cov; // Children are only covered (no cams), current node NOT covered
        res.cov = min({L.cam + RcovMin, R.cam + LcovMin}); // At least one of the children has cam
        res.cam = 1 + min(L.ncov, LcovMin) + min(R.ncov, RcovMin); // Children allowed to have any of 3 states
        
        //cout << res;
        
        return res;
    }
    
    int minCameraCover(TreeNode* root) {        
        ResultType root_status = DFS(root);        
        return min(root_status.cov, root_status.cam);
    }
};

 

<결론>

Optimal substructure 구조는 만족하나, Overlapping problem이 없기에 DP라고 하기엔 좀 그렇고,

그냥 DFS 문제.

 

각 노드의 가능한 상태를 내가 정의하고 관계를 정의한다는 점에서 새로웠음.

(익숙하지 않으면 이것도 힘들다)

 

어떻게 보면, 기존 노드에 제약을 추가해서 푸는 방법 (종만북 참고)