[백준/BOJ] 백준 9874번 : Wormholes

https://www.acmicpc.net/problem/9874

9874번: Wormholes

 

x축 방향으로 이동해서 도달할 수 있는 위치를 연결해서 그래프로 만들고, 만들어질 수 있는 웜홀 조합을 모두 만들어 보면서, 해당 웜홀 쌍에서 사이클이 존재하는지 확인했다.

사이클 판별 방법은, 각 지점을 모두 시작점으로 해보고, bfs를 통해 탐색하여 시작점으로 돌아오는 경우가 있는지 확인하는 방법으로 판별했다. 

 

코드

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

int n;
vector<pair<int, int>> point;
int result = 0;
vector<int> adj(15, -1);

//사이클이 존재하는지 확인
bool cycle(vector<int>& selected) {
	vector<int> wormhole(15, -1);

	//select를 기반으로 웜홀 연결을 만든다 select의 0번 인덱스<->1번 인덱스, 2번 인덱스<->3번 인덱스...
	for (int i = 0; i < selected.size(); i = i + 2) {
		int u = selected[i];
		int v = selected[i + 1];

		wormhole[u] = v;
		wormhole[v] = u;
	}

	//각 지점을 모두 시작점으로 해보며 탐색하고, 자기 자신으로 돌아오는게 있는지 확인
	for (int i = 0; i < n; i++) {
		int start = i;
		vector<int> moved_check(15, 0);
		queue<int> q;

		q.push(start);

		while (!q.empty()) {
			int here = q.front();
			q.pop();

			int moved_here = wormhole[here]; //here에서 웜홀로 이동되는 곳

			if (moved_check[moved_here] == 1) { //이전에 웜홀로 이동 되었던 위치일때
				return true;
			}

			moved_check[moved_here] = 1; //웜홀로 이동되는 곳 체크

			int there = adj[moved_here];

			if (there == -1) { //here에서 +x로 이동해서 도달 할 수 있는 위치가 없을때
				continue;
			}

			q.push(there);
		}

	}

	return false;
}

void solve(vector<int>& selected, vector<int>& check) {

	if (selected.size() == n) { //웜홀의 쌍을 모두 구했을때

		//싸이클이 존재하는지 확인
		if (cycle(selected)) {
			result++;
		}

		return;
	}

	int index1 = -1;
	for (int i = 0; i < n; i++) {
		if (check[i] == 0) { //웜홀의 쌍으로 선택되지 않은것을 발견했을때
			index1 = i;
			break;
		}
	}
	selected.push_back(index1);
	check[index1] = 1;

	//index1과 짝이 되는 웜홀의 인덱스(index2)를 골라서 확인해본다.
	for (int i = index1 + 1; i < n; i++) {
		if (check[i] == 1) {
			continue;
		}

		int index2 = i;

		selected.push_back(index2);
		check[index2] = 1;

		solve(selected, check);

		selected.pop_back();
		check[index2] = 0;
	}

	selected.pop_back();
	check[index1] = 0;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;

		point.push_back(make_pair(x, y));
	}

	//x축 기준으로 정렬
	sort(point.begin(), point.end());

	// 해당 위치에서 +x 방향으로 이동하면 도달하는 위치를 연결한다
	for (int i = 0; i < point.size(); i++) {
		for (int j = i + 1; j < point.size(); j++) {
			if (point[i].second == point[j].second && point[i].first < point[j].first) {
				adj[i] = j;
				break;
			}
		}
	}

	vector<int> selected;
	vector<int> check(n, 0);

	solve(selected, check);

	cout << result;

	return 0;
}