Gallery(감시카메라설치)

(출처) https://algospot.com/judge/problem/read/GALLERY

절단점으로 자르면 최소가 되지않을까?

문제에서 주어지는 예제를 보고 그래프의 절단점마다 감시카메라를 설치할 경우 원하는 답이 나오지 않을까라는 생각을 해보았다. 문제의 조건에서 사이클이 존재하지 않는다는 조건이 있기 때문에 절단점에 감시카메라를 배치하는 경우 완벽하게 모든 갤러리를 감시할 수 있어 보였다.

정점이 1개일 때와 정점이 2개일 때만을 예외로 두고 절단점을 구하여 전부 합하는 식으로 구현을 해보았는데 오답이 뜨더라.

다시 한번 생각해 보니 너무 많은 반례가 존재해 왜 안되는지 깊게 생각할 것도 없었다.

트리와 단순 경로

포기하고 책의 해답을 보니 주어진 갤러리가 사이클이 없다는 조건에 주목해 그래프를 트리로 확정해 두고 문제를 해결했다. 다른 그래프들과 다르게 트리구조의 그래프는 굉장히 직관적인 형태를 지니고 있다.

트리에 존재하는 모든 정점들은 오로지 자신의 부모 및 자식 정점들하고만 연결되어 있고, 다른 정점으로 이동하기 위해선 반드시 부모 혹은 자식 정점을 거쳐서 이동해야 한다. (자식들끼리 연결되어 있는 교차간선이나 자신의 부모보다 위에 있는 조상으로 바로 올라가버리는 역방향 간선 같은 것이 없다)

그렇기 때문에 두 정점을 잇는 단순경로는 오로지 단 하나만 존재한다. 따라서 다른 그래프들에 비해서 그래프의 탐색과정은 굉장히 직관적이고 예상하기 쉽다.

해당 문제에서 주어지는 갤러리 그래프는 시작점(루트)이 딱히 정해져있지 않는 루트 없는 트리 그래프이다.

우리는 갤러리에서 모든 정점을 지배할 수 있도록 감시카메라를 가장 최소화시키며 설치하는 것이 목표인데, 갤러리가 트리구조를 지니고 있기 때문에 가장 밑바닥 잎노드부터 시작해서 부모로 거슬러 올라가며 반드시 설치가 필요하다고 판단되는 지점에 1개씩 감시카메라를 추가하며 올라가는 과정을 거치면 원하는 답을 구해낼 수 있다.

만약 갤러리가 트리의 구조를 이루고 있지 않았다면 반드시 카메라를 추가해야 하는 지점을 판단하는 것이 모호해지지만, 갤러리가 트리의 구조를 이루고 있기 때문에 특정규칙을 정하면 반드시 카메라를 추가해야만 하는 지점을 확정할 수 있게 된다는 것이 이 문제의 포인트였다.

절단점 방식 코드(오답)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> camera;
vector<int> discoverd;
int cnt;
int INF = 99999999;

int gallery(vector<vector<int>> &adj, bool isRoot, bool isParentRoot, int here) {
	discoverd[here] = cnt++;
	int ret = discoverd[here];
	int child = 0;
	int subtree;
	for (int there = 0; there < adj[here].size(); there++) {
		if (adj[here][there] == 1) {
			if(discoverd[there] == -1) {
				child++;
				if (isRoot) isParentRoot = true;
				else isParentRoot = false;

				subtree = gallery(adj, false, isParentRoot, there);
				if (!isRoot && (subtree >= discoverd[here])) camera[here] = 1;
				ret = min(ret, subtree);
			}
			else ret = min(ret, discoverd[there]);
		}
	}

	if (isParentRoot && child == 0) {
		return INF;
	}
	if (isRoot) {
		if (child == 0 || child >= 2) {
			camera[here] = 1;
			return ret;
		}
		else if (child == 1 && subtree == INF) {
			camera[here] = 1;
			return ret;
		}
	}
	return ret;
}

int main() {
	int testcase;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> testcase;
	while (testcase--) {
		int g, h;
		cin >> g >> h;
		//그래프 만들기
		vector<vector<int>> adj(g, vector<int> (g, 0));
		for (int i = 0; i < h; i++) {
			int h_a, h_b;
			cin >> h_a >> h_b;
			adj[h_a][h_b]++;
			adj[h_b][h_a]++;
		}
		//각 정점을 시작점으로 탐색했을때 중단점(필요카메라개수)을 기록. 단 문제해결을 위해 정점이 1개인 경우, 정점이 2개인 경우도 중단점이 1개 있다고 판정한다.
		camera = vector<int> (g, 0);
		discoverd = vector<int> (g, -1);
		//나눠져있는 컴포넌트를 가정하여 전부 검사해야하므로 정점개수만큼 gallery함수를 돌려준다.
		for (int vertex = 0; vertex < g; vertex++) {
			if (discoverd[vertex] == -1) {
				cnt = 0;
				gallery(adj, true, false, vertex);
			}
		}
		// ret 세기
		int ret = 0;
		for (int i = 0; i < camera.size(); i++) {
			ret += camera[i];
		}
		cout << ret << "\n";

	}
	return 0;
}

책의 구현을 따라한 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int INSTALLED = 0;
const int UNINSTALLED = 1;
const int WATCHED = 2;
int camera;
vector<bool> visited;
vector<vector<int>> adj;

int gallery(int here) {
	visited[here] = true;
	int children[3] = { 0, 0, 0 };
	for (int there = 0; there < adj[here].size(); there++) {
		if (!visited[there] && adj[here][there] == 1) {
			++children[gallery(there)];
		}
	}

	if (children[UNINSTALLED]) {
		camera++;
		return INSTALLED;
	}
	else if (children[INSTALLED]) return WATCHED;
	//잎노드
	return UNINSTALLED;
}

int main() {
	int testcase;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> testcase;
	while (testcase--) {
		int g, h;
		cin >> g >> h;
		adj = vector<vector<int>> (g, vector<int> (g, 0));
		visited = vector<bool> (g, false);
		for (int i = 0; i < h; i++) {
			int h_a, h_b;
			cin >> h_a >> h_b;
			adj[h_a][h_b]++;
			adj[h_b][h_a]++;
		}

		camera = 0;
		for (int i = 0; i < g; i++) {
			if (!visited[i]) {
				int ret = gallery(i);
				if (ret == UNINSTALLED) camera++;
			}
		}

		cout << camera << "\n";
	}
	return 0;
}

기억하고 싶은 점

사이클이 없으며 모든 정점 V 개가 연결된 그래프는 간선이 V-1 개가 되며 무조건 트리 형태가 된다. 그리고 트리 형태는 두 정점이 반드시 하나의 단순경로를 갖는다.

위와 같은 트리의 구조, 특성을 가지고 있는 트리의 정점들의 연결관계는 직관적으로 느끼기 쉽다. 그리고 직관적인 만큼 조작해 먹을(이용해 먹을) 요소들이 많다는 걸 느끼는 것이 중요해 보인다.