Gallery: 감시 카메라 설치

문제링크: 감시 카메라 설치

갤러리에 갔다 돌아오려면 다시 지나가야 하므로, 싸이클이 없는 그래프가 된다. 

처음에는 제일 많은 자식노드를 가진 노드에 카메라를 설치하도록 생각해서 구현했는데

그렇게 되면 최적화가 안되는 경우가 있었다. =ㅁ=;;

역시.. 손으로 검증을 다 해보고 구현해야..

리프노드가 있는 경우 그 부모에 무조건 카메라를 설치한 후, 나머지 노드에 설치하면 된다.

리프노드 전 노드에 카메라를 설치하지 않으면 리프노드에 어차피 카메라를 설치해야 하기 때문에

리프노드의 부모노드는 무조건 설치해야 한다. 

dfs로 트리를 방문하면서 

1. 자식들 중에 커버되지 않는 자식을 가지고 있으면, 현재 방에 카메라를 설치한다. 

2. 자식들 중에 카메라가 설치되어 있는 방이 있으면, 현재 방에는 카메라를 설치할 필요없이 커버된다. 

3. 나머지는 커버되지 않는 곳을 마킹해 둔다. 

중복으로 방문하지 않도록 재귀호출 시, 상태를 변경해두었다. 

마지막으로, 자식이 없는 노드의 경우 모두 카메라를 설치할 수 있도록 한다. 

두가지 키. 

1. 무향 그래프가 되도록 삽입한다. 

2. 자식들을 살펴본 후 결정한다.

#include <iostream>
using namespace std;
 
// 감시카메라 설치
int C, G, H;
int Edge[1001][1001];
int Gallery[1001];
int Camera = 0;
const int NOTVISITED = -1;
const int UNCOVERED = 0;
const int COVERED = 1;
const int INSTALLED = 2;
 
 
void init() {
    // init
    for (int i = 0; i < G; i++) {
        Gallery[i] = NOTVISITED;
        Edge[i][0] = 0;
    }
    Camera = 0;
}
int solve(int here) {
    int ret;
    Gallery[here] = UNCOVERED;
    // UNCOVERED, COVERED, INSTALLED
    int children[3] = { 0, };
    for (int i = 1; i <= Edge[here][0]; i++) {
        if (Gallery[Edge[here][i]] == NOTVISITED) {
            ret = solve(Edge[here][i]);
            children[ret]++;
        }
    }
    // 자식이 uncovered 가 있으면, 현재 방에 카메라 설치
    if (children[UNCOVERED]) {
        Gallery[here] = INSTALLED;
        Camera++;
    }
    // 자식 중 하나가 설치되어 있으면 현재 방에 카메라 설치할 필요없음
    else if (children[INSTALLED]) {
        Gallery[here] = COVERED;
    }
    else 
        Gallery[here] = UNCOVERED;
    return Gallery[here];
}
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> G >> H;
        init();
 
        for (int h = 0; h < H; h++) {
            int a, b;
            cin >> a >> b;
 
            Edge[a][++Edge[a][0]] = b;
            Edge[b][++Edge[b][0]] = a;
        }
 
        for (int i = 0; i < G; i++) {
            if (Gallery[i] == NOTVISITED)
                // 노드가 1개인 경우, 카메라를 무조건 설치함
                if (solve(i) == UNCOVERED)
                    Camera++;
 
        }
        cout << Camera << endl;
    }
}