감시카메라 GALLERY

<출처> 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2권

 

AOJ 감시카메라 GALLERY

 

SOL)

이 문제는 문제에서 주어진 조건을 잘 읽으면 사이클이 없고

트리형태라는 것을 알 수가 있다.

DFS탐색을 통해 leaf부터 하나 씩 올라가면서 해당 정점에서

카메라를 설치를 할지 안할지 결정을 하는 것이 가장 좋다.

결정 방법은 자기 자식 노드가 카메라의 감시를 받고 있지 않다면

그 정점에는 카메라를 반드시 설치해야 하는 것이다.

(이런 식으로 생각을 했지만 구현하는 것이 어려웠다..)

 

<소스 코드>

[-] Collapse

#include<cstdio>
#include<vector>
using namespace std;

int V;
vector<vector<int> > adj;
vector<bool> visited;
const int UNWATCHED = 0;
const int WATCHED = 1;
const int INSTALLED = 2;

int installed;

int dfs(int here) {
    visited[here] = true;
    int children[3] = { 0, 0, 0 };
    for (int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        if (!visited[there])
            ++children[dfs(there)];
    }
    if (children[UNWATCHED]){
        ++installed;
        return INSTALLED;
    }
    if (children[INSTALLED])
        return WATCHED;
    return UNWATCHED;
}

int installCamera(){
    installed = 0;
    visited = vector<bool>(V, false);
    for (int u = 0; u < V; u++){
        if (!visited[u] && dfs(u) == UNWATCHED)
            ++installed;
    }
    return installed;
}

int main(){
    int T; scanf("%d", &T);
    while (T--){
        int n; scanf("%d%d", &V, &n);
        adj = vector<vector<int> >(V);
        for (int i = 0; i < n; i++){
            int u, v; scanf("%d%d", &u, &v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        printf("%d\n", installCamera());
    }
}