감시 카메라 설치

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

코드( C ++ ) 종만북 참조

문제

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

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

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

const int MAX = 1000 + 1;

vector<int> gallery[MAX];

const int UNWATCHED = 0;

const int WATCHED = 1;

const int INSTALLED = 2;

int g, h;

// 지금까지 설치한 카메라의 총 수

int installed;

vector<bool> visited;

// here로 부터 깊이 우선 탐색을 하고, here의 정보를 반환한다.

int dfs(int here)

{

visited[here] = true;

int check[3] = { 0,0,0 };

for (int i = 0; i < gallery[here].size(); ++i)

{

int there = gallery[here][i];

if (!visited[there]) {

++check[dfs(there)];

}

}

// 자손 노드 중 감시되지 않는 노드가 있을 경우 카메라를 설치한다.

if (check[UNWATCHED])

{

installed++;

return INSTALLED;

}

// 자손 노드 중 카메라가 설치된 노드가 있을 경우 설치할 필요가 없다.

if (check[INSTALLED])

{

return WATCHED;

}

return UNWATCHED;

}

// 그래프를 감시하는데 필요한 카메라의 최소 수를 반환한다.

int InstallCamera()

{

installed = 0;

visited = vector<bool>(g, false);

for (int u = 0; u < g; ++u) {

if (!visited[u] && dfs(u) == UNWATCHED)

{

installed++;

}

}

return installed;

}

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> g >> h;

int u, v;

for (int i = 0; i < h; ++i)

{

cin >> u >> v;

gallery[u].push_back(v);

gallery[v].push_back(u);

}

cout << InstallCamera() << endl;

for (int i = 0; i < g; ++i) {

gallery[i].clear();

}

}

}