[Algospot] 감시 카메라 설치 (문제 ID : GALLERY)

문제

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

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

 

입력

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

 

출력

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

---

그래프를 활용한 dfs 문제이다. 

복도가 연결 된 갤러리 중 방문안한 갤러리를 방문하는 dfs의 개념은 쉽지만, 

갤러리와 연결된 지점들에 cctv가 설치 되었는지, 감시중인지, 감시가 안 되는지 판단하는 건 쉽지 않았다.

dfs 내에서 child배열을 이용해 반환 값을 조정하는 걸 유의해서 보자.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/GALLERY.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int C, G, H, res;
int p[1001][1001];
int check[1001];
const int UNWATCHED = 0;
const int WATCHED = 1;
const int INSTALLED = 2;

int dfs(int x) { 
	check[x] = true;
	int child[3] = { 0,0,0 };
	for (int i = 0; i < G; i++) {
		if (!check[i] && p[x][i] == 1) 
			++child[dfs(i)];
	}
	//설치 안된 자손이 있는 경우 x에 설치
	if (child[UNWATCHED]) {
		++res;
		return INSTALLED;
	}
	//모든 자손이 감시 중이고, 설치된 게 있으면 x도 감시중
	if (child[INSTALLED]) {
		return WATCHED;
	}

	//모든 자손이 감시중이기만 하면 x는 감시 안됨
	return UNWATCHED;
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> G >> H;
		memset(p, 0, sizeof(p));
		memset(check, 0, sizeof(check));

		for (int a, b, i = 0; i < H; i++) {
			cin >> a >> b;
			p[a][b] = p[b][a] = 1; //a와 b지점이 연결됐다.
		}
		
		res = 0;
		for (int i = 0; i < G; i++) {
			if (!check[i]) {
				if (dfs(i) == 0) res++;
			}
		}
		cout << res << "\n";
	}
}