GALLERY 감시 카메라 설치

문제

전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 프로게이머의 얼굴로 합성하겠다는 것입니다. 미술관의 관장을 맡고 있는 재하는 이와 같은 사태를 방지하기 위해 감시 카메라를 설치하기로 마음먹었습니다. 미술관은 여러 개의 갤러리와 이들을 연결하는 복도로 구성되어 있으며, 한 갤러리에 감시 카메라를 설치하면 이 갤러리와, 복도로 직접 연결된 갤러리들을 감시할 수 있습니다. 모든 갤러리를 감시하기 위해 필요한 최소 감시 카메라의 수는 몇 개일까요?

미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며, 모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 미술관에 포함된 갤러리의 수 G (1 <= G <= 1000) 와 갤러리들을 연결하는 복도의 수 H (0 <= H < G) 가 주어집니다. 각 갤러리에는 0번부터 G-1 번까지의 고유 번호가 있습니다. 그 후 H 줄에 각 2개의 정수로 각 복도가 연결하는 두 갤러리의 번호가 주어집니다.

출력

각 테스트 케이스마다 한 줄에 필요한 카메라의 최소 개수를 출력합니다.

어려웠다. 책의 코드를 보았는데도  한 번에 이해하기가 어려웠다. 

이 문제의 핵심은 경우의 수를 3가지로 생각하는 점이다.

https://algospot.com/judge/problem/read/GALLERY

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
const int WATCHED = 0;
const int UNWATCHED = 1;
const int INSTALLED = 2;
 
bool visit[1001] = { false, };
 
int C = 0, H = 0, G = 0;
 
int install = 0;
 
vector<vector<int> > v;
 
int DFS(int start)
{
    visit[start] = true;
 
    bool child[3] = { false, false, false };
 
    for (int next : v[start])
    {
        if (!visit[next])
        {
            child[DFS(next)] = true;
        }
    }
 
    // 감시되고 있지 않다면, 감시 카메라 갯수 1 증가 및 '설치됨' return
    if (child[UNWATCHED])
    {
        ++install;
 
        return INSTALLED;
    }
 
    // 이미 설치가 되었다면, 이미 '감시 당함'이므로, return
    if (child[INSTALLED])
    {
        return WATCHED;
    }
 
    // 위의 2개가 아니라면
    return UNWATCHED;
}
 
int main(void)
{
    int start_vertex = 0, end_vertex = 0;
 
    scanf("%d", &C);
 
    for (int tc = 1; tc <= C; tc++)
    {
        scanf("%d %d", &G, &H); // G : 갤러리의 수, H : 복도의 수
 
        v.resize(G);
 
        while (H--)
        {
            scanf("%d %d", &start_vertex, &end_vertex);
 
            v[start_vertex].push_back(end_vertex);
            v[end_vertex].push_back(start_vertex);
        }
 
        for (int i = 0; i < v.size(); i++)
        {
            sort(v[i].begin(), v[i].end());
        }
 
        for (int i = 0; i < G; i++)
        {
            if (!visit[i] && DFS(i) == UNWATCHED)
            {
                ++install;
            }
        }
 
        printf("답 : %d\n", install);
 
        install = 0;
 
        memset(visit, false, sizeof(visit));
 
        for (int i = 0; i<G; i++)
        {
            if(!v[i].empty()) v[i].clear();
        }
    }
    
    return 0;
}