์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ํŽ˜์–ด๋ง ์Œ์„ ๋งŒ๋“ค๊ณ , ์‚ฌ์ดํด์ด ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ์ž‘์—…์„ ๋ชจ๋“  ํŽ˜์–ด๋ง ์Œ์„ ๋Œ€์ƒ์œผ๋กœ ํ•˜๋ฉด ๋จ.
  • ํ—ค๋ฉ˜ ๋ถ€๋ถ„
    1. ์‚ฌ์ดํด์„ ์ฐพ์„๋•Œ ๊ฐ™์€ ํŽ˜์–ด๋ง์Œ์„ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•˜๋Š”๊ฒŒ ์•„๋‹ˆ๋ผ, ๊ฐ™์€ ์ ์„ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•˜๋Š”์ง€ ํ™•์ธํ•ด์•ผํ•จ.
    2. check ๋ฅผ ์–ธ์ œ ์ดˆ๊ธฐํ™”ํ•ด์•ผํ•˜๋Š”์ง€ ํ—ท๊ฐˆ๋ฆผ โ†’ ํ™•์‹คํžˆํ•˜๋ ค๋ฉด ๋งค ์‹œ์ž‘์ ๋งˆ๋‹คํ•˜๋ฉด ๋จ.

์—ฌ๋‹ด

  • ์ถœ์ฒ™ Olympiad> USA Computing Olympiad ์ธ๋ฐ, ์š”์ฆ˜ ์ด ์ถœ์ฒ˜์˜ ๋ฌธ์ œ๋“ค์„ ํ’€๋ฉด์„œ ๋А๋‚€ ๊ฒŒ, ์ด ์ถœ์ฒ˜์˜ ๋ฌธ์ œ๋“ค์€ ๋‚ด์šฉ์ž์ฒด๋Š” ๊ฐ„๋‹จํ•œ๋ฐ, ์˜ˆ์™ธ ๋˜๋Š” ํŠน์ˆ˜ํ•œ ๊ฒฝ์šฐ ์ฒ˜๋ฆฌ๊ฐ€ ๋งค์šฐ ์–ด๋ ต๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  ๋‚ด๊ฒ ํ•œ๋ฒˆ โ€˜ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค.โ€˜๊ฐ€ ๋œจ๋ฉด ๊ธฐ์กด ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์ง‘์ฐฉํ•ด์„œ ์ƒˆ๋กœ์šด ์ƒ๊ฐ์„ ๋ชปํ•˜๋Š” ๋‹จ์ ์ด ์žˆ๋Š”๊ฑฐ ๊ฐ™๋‹ค.
  • ์•ž์œผ๋กœ๋Š” ๋ฌธ์ œํ’€๋•Œ ๋ฐฐ์—ด ๋ฒ”์œ„๋ฌธ์ œ๋Š” ์ผ์–ด๋‚˜์ง€ ์•Š๋„๋ก ํฌ๊ฒŒ ๋‘๊ณ , ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค๊ฐ€ ๋œจ๋ฉด ๊ธฐ์กด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์žฌ์ ๊ฒ€ํ•˜๊ณ , ๋ฌธ์ œ ์—†์„๊ฒฝ์šฐ ์ง€์ฒด์—†์ด ํŠน์ˆ˜ํ•œ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ด์•ผ๊ฒ ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define INF 2000000000
 
using namespace std;
 
int n, holes[15][2], ans, pairing[7][2];
bool visit[15], check[8][2];
 
void makePair(int cur, int deep);
bool findCycle(int s, int o);
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> holes[i][0] >> holes[i][1];
 
	visit[0] = true;
	makePair(0, 0);
 
	cout << ans;
}
 
void makePair(int cur, int deep) {
	if (deep == n / 2) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n / 2; j++)
				if (findCycle(j, i)) {
					ans++;
					return;
				}
		}
		return;
	}
	pairing[deep][0] = cur;
	for (int i = cur + 1; i < n; i++) {
		if (!visit[i]) {
			visit[i] = true;
			pairing[deep][1] = i;
			int j = 0;
			for (; j < n; j++)
				if (!visit[j])
					break;
			visit[j] = true;
			makePair(j, deep + 1);
			visit[i] = false;
			visit[j] = false;
		}
	}
}
 
 
bool findCycle(int s, int o) {
	int next = pairing[s][!o];
	check[s][o] = true;
 
	while (next != -1) {
		int cur = next;
		next = -1;
 
		int cr = holes[cur][1], cc = holes[cur][0], ni, nj, close = INF;
		for (int i = 0; i < n / 2; i++) {
			for (int j = 0; j < 2; j++) {
				if (cr == holes[pairing[i][j]][1] && cc < holes[pairing[i][j]][0] && holes[pairing[i][j]][0] < close) {
					close = holes[pairing[i][j]][0];
					ni = i;
					nj = j;
				}
			}
		}
 
		if (close != INF) {
			if (check[ni][nj]) {
				memset(check, 0, sizeof(check));
				return true;
			}
			check[ni][nj] = true;
			next = pairing[ni][!nj];
		}
	}
	memset(check, 0, sizeof(check));
	return false;
}