[algospot] PICNIC

https://algospot.com/judge/problem/read/PICNIC

코드 개요

완전 탐색을 이용하여 해결하는 문제로, 친구들의 관계를 2차원 배열 areFriends로 표현한 후, 가능한 모든 쌍을 찾을 때까지 친구의 짝을 짓는 재귀를 반복한다.

코드

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

int n, m, t, a, b;
bool areFriends[10][10]; // 친구들 관계

int solution(bool taken[10])
{
	int front = -1; // 중복 제거를 위해 작은 수가 왼쪽에 오도록 함
	for (int i = 0; i < n; i++)
	{
		if (!taken[i])
		{
			front = i;
			break;
		}
	}

	if (front == -1)
		return 1;
	int cnt = 0;
	for (int i = front + 1; i < n; i++)
	{
		if (!taken[i] && areFriends[front][i])
		{
			taken[front] = taken[i] = true;
			cnt += solution(taken);
			taken[front] = taken[i] = false;
		}
	}
	return cnt;
}

int main(void)
{
	
	cin >> t;
	while (t--)
	{
		bool taken[10] = { false };
		memset(areFriends, false, sizeof(areFriends));
		
		cin >> n >> m;
		
		for (int i = 0; i < m; i++)
		{
			cin >> a >> b;
			areFriends[a][b] = true;
			areFriends[b][a] = true;
		}
		
		cout << solution(taken)<<endl;
	}
	return 0;
}