algospot 감시 카메라 설치(문제 ID: GALLERY) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/GALLERY

algospot.com :: GALLERY

그래프에서 인접한 노드중에 적어도 하나의 노드에 감시카메라가 설치되어있지 않으면 해당 노드에 감시카메라를 설치 해야한다.

이때 필요한 최소한의 감시카메라의 개수를 구하는 문제이다.

 

문제 조건에서 "미술관은 한 번 관람한 갤러리를 다시 가기 위해서는 이전에 지나왔던 복도를 반드시 한 번 지나야 하는 구조로 설계되어 있으며"가 있으므로 해당 그래프는 트리형태임을 알 수 있다.

따라서 자손 노드들의 상태를 보고 하나라도 UNWATCHED상태라면 해당 노드에 감시카메라를 설치하는 알고리즘을 사용할 수 있다.

또한 "모든 갤러리가 서로 연결되어 있지 않을 수도 있습니다."라는 조건이 있으므로 모든 노드가 방문되었는지 확인하는 절차도 필요하다.

 

	#include<iostream>
	#include<vector>
	using namespace std;
	vector<int> adj[1000];
	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(int v) {
	installed = 0;
	visited = vector<bool>(v, false);
	// 여러개의 컴포넌트들이 있을 수 있으므로 전체 갤러리 확인
	// 루트갤러리가 UNWATCHED상태라면 루트에 카메라 설치가 필요
	for (int i = 0; i < v; i++)
	if (!visited[i] && dfs(i) == UNWATCHED)
	installed++;
	return installed;
	}
	void makeGraph(int h) {
	for (int i = 0; i < h; i++) {
	int u, v;
	cin >> u >> v;
	adj[u].push_back(v);
	adj[v].push_back(u);
	}
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	int g, h;
	cin >> g >> h;
	for (int i = 0; i < 1000; i++)
	adj[i].clear();
	makeGraph(h);
	cout << installCamera(g) << endl;
	}
	}

view raw algospot 감시 카메라 설치(문제 ID: GALLERY).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/GALLERY.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2