알고스팟 - 소풍 (PICNIC) [C++]

 이 문제는 완전 탐색으로 해결할 수 있다. 아주 간단하게 계산하면 10! ~= 3,000,000 정도밖에 안된다. 그러나 이 문제의 경우 쌍을 골라야 하고, 순서만 바뀐 경우는 제외해야 하므로 경우의 수가 훨씬 줄게 된다. 그래서 완전 탐색으로도 가능한 문제였다.

 

#include <iostream>

using namespace std;

#define MAX 10

int n, m;
bool isFriend[MAX][MAX];
bool matched[MAX];

int solve(int matchCount, int prev) {
	if (matchCount == n) {
		return 1;
	}

	if (prev == -1) {
		int result = 0;
		for (int i = 0; i < n; i++) {
			if (matched[i]) {
				continue;
			}

			for (int j = i + 1; j < n; j++) {
				if (!matched[j] && isFriend[i][j]) {
					matched[i] = true;
					matched[j] = true;
					result += solve(matchCount + 2, i);
					matched[i] = false;
					matched[j] = false;
				}
			}
		}

		return result;
	}

	int result = 0;
	for (int i = prev + 1; i < n; i++) {
		if (matched[i]) {
			continue;
		}

		for (int j = i + 1; j < n; j++) {
			if (!matched[j] && isFriend[i][j]) {
				matched[i] = true;
				matched[j] = true;
				result += solve(matchCount + 2, i);
				matched[i] = false;
				matched[j] = false;
			}
		}
	}

	return result;
}

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			isFriend[i][j] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		cin >> n >> m;

		init();

		for (int i = 0; i < m; i++) {
			int a, b;

			cin >> a >> b;

			isFriend[a][b] = true;
			isFriend[b][a] = true;
		}

		cout << solve(0, -1) << '\n';
	}

	return 0;
}