[BOJ] 백준 16491번: 대피소 찾기

CCW를 이용한 선분 교차 판별 알고리즘을 통해 DFS 탐색하는 문제

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;
typedef pair<int, int> pii;
int n;
int rsy[101] = { 0, }; // 같은 y좌표를 갖는 로봇
int dsy[101] = { 0, }; // 같은 y 좌표를 갖는 대피소
pii pr[101];
pii pd[101];
int tmp[101];
bool visit[101];
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
	int left = x1 * y2 + x2 * y3 + x3 * y1;
	int right = x1 * y3 + x3 * y2 + x2 * y1;
	int dif = left - right;
	if (dif == 0) return 0; // 일직선
	return (dif > 0 ? 1 : -1); // 반시계, 시계
}
bool overlap(pii aa, pii ab, pii ba, pii bb) { // 접하면 true, 접하지 않으면 false;
	int fccw = ccw(aa.first, aa.second, ab.first, ab.second, ba.first, ba.second);
	int sccw = ccw(aa.first, aa.second, ab.first, ab.second, bb.first, bb.second);

	int _fccw = ccw(ba.first, ba.second, bb.first, bb.second, aa.first, aa.second);
	int _sccw = ccw(ba.first, ba.second, bb.first, bb.second, ab.first, ab.second);

	int left = fccw * sccw;
	int right = _fccw * _sccw;
	if (left <= 0 && right <= 0) {
		if (left == 0 && right == 0) {
			if (aa > ab) {
				swap(aa, ab);
			}
			if (ba > bb) {
				swap(ba, bb);
			}
			return (aa <= bb && ba <= ab);
		}
		else {
			return true;
		}
	}
	return false;
}
// dfs
bool dfs(int node,int level) {
	if (node == n+1) {
		for (int i = 1; i <= n; i++) {
			cout << tmp[i] << "\n";
		}
		return true;
	}
	for (int i = 1; i <= n; i++) {
		if (!visit[i]) {
			int flag = 1;
			for (int j = 1; j <= level; j++) {
				// j와 tmp[level] 과 node와 i가 겹치는지 
				//cout << pr[j].first << "," << pr[j].second << " ," << pd[tmp[j]].first << "," << pd[tmp[j]].second << " <> " << pr[node].first << "," << pr[node].second << " ," << pd[i].first << "," << pd[i].second << "\n";
				if (overlap(pr[j], pd[tmp[j]], pr[node], pd[i])) {
					//cout << "겹쳐~\n";
					flag = 0;
					break;
				}
			}
			if (flag) {
				visit[i] = 1;
				tmp[node] = i;
				if (dfs(node + 1, level + 1)) {
					return true;
				}
				visit[i] = 0;
			}
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		rsy[y] += 1;
		pr[i] = { x,y };
	}
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		dsy[y] += 1;
		pd[i] = { x,y };
	}
	for (int i = 1; i <= n; i++) {
		visit[i] = 1;
		tmp[1] = i;
		if (dfs(2, 1)) {
			break;
		}
		visit[i] = 0;
	}
}