28.8 문제: 감시 카메라 설치(문제 ID: GALLERY)

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

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

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

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

예제 입력
3
6 5
0 1
1 2
1 3
2 5
0 4
4 2
0 1
2 3
1000 1
0 1

예제 출력
3
2
999

🤔생각

이 문제에서는 무방향 그래프이고 조건으로 인해서 트리간선만 존재하게 된다.처음에는 한 정점에서 연결된 간선 수가 많은 곳 부터 카메라를 설치하면 된다고 생각했다. 하지만 이런 생각에는 반례가 존재했다. 그래서 다른 방법을 생각해냈다. DFS를 통해 어떤 정점에서 사용되지 않은 간선이 0개 이면 그 정점의 부모에 카메라를 달고 부모와 연결된 모든 간선을 제거하는 방식으로 풀려고 했다. 하지만 생각을 코드로 구현하지는 못했다. 그래서 책의 아이디어를 참고하여 구현해보았다.

😀코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int V, cnt;
vector<vector<int>> adj;
vector<int> visited, on, can;

void DFS(int here, bool isRoot) {
	visited[here] = true;

	int childrenCan = 1;

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (!visited[there]) {
			DFS(there, false);

			childrenCan = childrenCan && can[there];

			if (on[there] == 1)
				can[here] = true;
		}
	}

	if (childrenCan == 0) {
		can[here] = true;
		on[here] = true;
		cnt++;
	}
	if (isRoot && !can[here])
		cnt++;
}

int solve(int G) {
	cnt = 0;
	visited = on = can = vector<int>(G, false);

	for (int i = 0; i < G; i++)
		if (visited[i] == false)
			DFS(i, true);

	return cnt;
}

int main(void) {
	int C, H, G, p1, p2;

	cin >> C;

	while (C--) {
		cin >> G >> H;
		adj = vector<vector<int>>(G);

		for (int i = 0; i < H; i++) {
			cin >> p1 >> p2;

			adj[p1].push_back(p2);
			adj[p2].push_back(p1);
		}

		cout << solve(G) << endl;
	}

	return 0;
}

👏후기

사이클이 존재하지 않는 그래프는 노드 간의 상하관계가 없는 트리형태인데 이것이 루트 없는 트리라는 것이며 이럴 때는 스패닝 트리를 통해 해결한 다는 것, 트리의 최소 지배 집합을 찾는 가장 간단한 방법은 트리의 맨 아래부터 시작해서 위로 올라오는 것 등 유용하고 효과적인 방법을 알게 되었다.