브루트포스 155p 소풍

 

algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

친구끼리만 짝이 되게끔 만들어야 한다. 

친구끼리만 짝이 되는 경우의 수는?

 

모든 경우를 다 따진 후에 친구끼리만 짝 되었을 때 세면 된다.

 

brute force 를 사용할 수 있는 경우는 입력이 작아서, 시간초과가 나지 않을때는 가능한 것 같다. 

위 문제는 이걸 위해서 만들어진 문제기 때문에 상관없다만 조심하자 

 

아 그리고 또 항상 주의해야 할것이 중복되게 세지 않는 것이다. 중복이 생기는 순간 원하는 답을 얻을 수 없다.

 

이건 잘 생각해서 어떤 방향으로 채워나갈지 진행할지 생각하고 코드 짜자.

 

 

 

#include<iostream>
using namespace std;
#define MAX 15

int C, n, m;
bool fr[MAX][MAX] = { false, };
bool done[MAX] = { false, };

int matching(int num) {
	if (num == 0) {
		return 1;
	}
	int ret = 0;
	int one = -1;
	for (int i = 0; i < n; i++) {
		if (!done[i]){
			one = i;
			break;
		}
	}
	for (int i = one + 1; i < n; i++) {
		if (done[i]) continue;
		if (fr[one][i]) {
			done[one] = true;
			done[i] = true;
			ret += matching(num - 2);
			done[one] = false;
			done[i] = false;
		}
	}

	return ret;
}

int main() {
	cin >> C;
	while (C--) {
		for (int i = 0; i < MAX; i++) {
			done[i] = false;
			for (int j = 0; j < MAX; j++) {
				fr[i][j] = false;
			}
		}
		cin >> n >> m;
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			fr[a][b] = true;
			fr[b][a] = true;
		}
		
		cout << matching(n) << "\n";
	}
}