[백준OJ] 5884번 감시카메라

www.acmicpc.net/problem/5884

5884번: 감시 카메라

---

 

-풀이-

DFS를 이용하여 모든 경우를 조사하며 풀었다.

현재 존재하는 선분들이 담긴 벡터를 탐색하며,

 

1.현재 점이 존재하는 선분들중 하나에 포함이 되는 경우

 선을 추가할것 없이 dfs수행을 해주면된다.

 

2.아닌 경우

 해당 점을 통과하는 x축과 y축에 대해 각각 dfs를 수행 해주면 된다.

 

여기서 중요한것은

1. 이미 정답을 찾은경우는 더이상 dfs를 수행하지 않아도 된다.

2. 만약 현재 존재하는 선분들의 개수가 4개 이상이 된다면, 그 길은 이미 틀린길이라 return 해준다.

3. 만약에 선분이 3개 이하이면서, 마지막원소까지 검사를 다 마쳤다면, 정답이 되므로 정답을 찾았다는 체크를 해준뒤, return 해준다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n;
int arrx[50000];
int arry[50000];
bool result = false;

void dfs(int cnt, vector<pair<int, int>> l) {
	//정답이 나왔으면 dfs수행 필요x
	if (result) {
		return;
	}

	//선이 3개 이상이면 리턴
	if (l.size() > 3) {
		return;
	}

	//n개를 다 탐색했는데도 3개 이하이면 정답
	if (cnt == n) {
		result = true;
		return;
	}

	//처음 넣는것은 x축에 대한 dfs, y축에 대한dfs실행
	if (cnt == 0) {
		l.push_back({ arrx[0],-1 });
		dfs(cnt + 1, l);
		l.pop_back();
		l.push_back({ -1,arry[0] });
		dfs(cnt + 1, l);
	}
	else {
		bool flag = false;

		//현재 존재하는 선을 돌며
		for (int i = 0; i < l.size(); i++) {
			//x좌표가 같으면 선을 추가할 필요 없이 다음 cnt dfs실행
			if (l[i].first == arrx[cnt]) {
				flag = true;
				dfs(cnt + 1, l);
				break;
			}
			//y좌표가 같아도 선을 추가할 필요 x,위와 동
			if (l[i].second == arry[cnt]) {
				flag = true;
				dfs(cnt + 1, l);
				break;
			}
		}
		//현재 존재하는 선들과 수평/수직이 아닌경우
		if (!flag) {
			//선을 추가해준뒤, dfs실행
			l.push_back({ arrx[cnt],-1 });
			dfs(cnt + 1, l);
			l.pop_back();

			l.push_back({ -1,arry[cnt] });
			dfs(cnt + 1, l);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arrx[i] >> arry[i];
	}

	if (n <= 3) {
		cout << "1\n";
		return 0;
	}

	vector<pair<int, int>> l;
	dfs(0, l);

	cout << result << "\n";
}