[알고리즘] 알고스팟 PICNIC 문제

알고리즘을 통한 문제 해결전략 6과

- 재귀 함수 이용

- 중복으로 세는 경우, 사전순으로 하여  답 하나만 세도록 한다.

 

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

int n; // the number of students
bool areFriends[10][10] = { false, };

int countPairings(bool taken[10]);

int main() {
	int testcase;
	int pair;
	int f1, f2;
	vector<int> answer;

	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		//areFriends false로 다시 초기화
		for (int m = 0; m < 10; m++) {
			for (int p = 0; p < 10; p++) {
				areFriends[m][p] = false;
			}
		}
		//taken[i] : i번쨰 학생이 짝을 찾았으면 true, 아니면 false
		bool taken[10] = { false, };

		cin >> n >> pair;
		
		for (int j = 0; j < pair; j++) {
			cin >> f1 >> f2;
			areFriends[f1][f2] = true;
			areFriends[f2][f1] = true;
		}

		answer.push_back(countPairings(taken));
	}

	for (vector<int>::iterator itr = answer.begin(); itr != answer.end(); ++itr) {
		cout << *itr << endl;
	}
}

int countPairings(bool taken[10]) {
	//남은 학생들 중 가장 번호가 빠른 학생 찾기
	int firstFree = -1;
	for (int i = 0; i < n; ++i) {
		if (!taken[i]) {
			firstFree = i;
			break;
		}
	}

	//base case: 모든 학생이 짝을 찾았으면 한가지 방법 찾았으니 종료
	if (firstFree == -1) return 1;
	int ret = 0;
	
	//이 학생과 짝지을 학생수 결정
	for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
		if (!taken[pairWith] && areFriends[firstFree][pairWith]) {
			taken[firstFree] = taken[pairWith] = true;
			ret += countPairings(taken);
			taken[firstFree] = taken[pairWith] = false;
		}
	}
	return ret;
}