소풍 - 완전 탐색

문제

 

n명의 학생들이 소풍 때 두 명씩 짝을 지어 행동하게 하려고 한다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 한다.

입력 값으로 학생의 수와 친한 친구 관계가 주어졌을 때, 학생들을 짝 지을 수 있는 방법의 수를 출력하시오.

 

짝 지을 수 있는 모든 방법의 수를 탐색하여 친한 친구 관계만 체크해서 해결 할 수 있다.

 

문제를 해결하는 포인트는 재귀적으로 두 학생을 짝 지어주는 경우의 수를 계산하는 동작

 

bool areFriends[10][10];
bool taken[10];

int countPairings(bool* taken, int n)
{
	int ret = 0;
	int mark = -1;

	// 현재 마크가 아닌 학생 찾기
	for(int i = 0; i < n; ++i) 
	{
		if(!taken[i]) 
		{
			mark = i; 
			break;
		}
	}

	// 모두 마크된 경우, 한 가지 방법(경우의 수)를 찾음
	if(mark == -1) return 1;

	// 위에서 찾은 학생을 마킹
	taken[mark] = true;

	// 마킹된 학생과 짝이 가능한 학생 탐색
	for(int i = mark+1; i < n; ++i)
	{
		// 둘이 친구관계이며, 아직 마킹이 안되어 있다면
		if (areFriends[mark][i] && taken[i] == false)
		{
			taken[i] = true;
			ret += countPairings(taken, n);
			taken[i] = false;
		}
	}

	taken[mark] = false;

	return ret;
}

int main()
{
	int testcase;
	scanf("%d", &testcase);

	for(int t = 0; t < testcase; ++t)
	{
		fill(areFriends[0], areFriends[0]+100, false);
		fill(taken, taken+10, false);

		int n;
		int numberOfCase;
		scanf("%d %d", &n, &numberOfCase);

		for (int i = 0; i < numberOfCase; ++i)
		{
			int c1, c2;
			scanf("%d %d", &c1, &c2);
			areFriends[c1][c2] = areFriends[c2][c1] = true;

		}

		cout << countPairings(taken, n) << endl;
	}

	return 0;
}