무식하게 풀기(Brute force) - 2. 소풍

문제 : 소풍 (난이도 下)

 

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

 

위 문제를 '무식하게' 풀어보자.

 

문제 분석

 

예제 입력을 보면 친구 관계가 순서쌍으로 주어진다.

 

2번째 케이스를 예로 들면 다음과 같이 표현할 수 있다.

 

(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3)

 

이를 4x4 Matrix로 친구 관계를 나타내면 다음과 같다.

 

	0	1	2	3
0		Friend	Friend	Friend
1	Friend		Friend	Friend
2	Friend	Friend		Friend
3	Friend	Friend	Friend

 

이 문제는 '중복'을 방지하는 것이 핵심이다.

 

1. (0, 1)과 (1, 0)는 이 문제에서 같은 순서쌍이다.

2. <(0, 1), (1, 2)>와 <(1, 2), (0, 1)>은 같은 경우이다.  

 

위 중복을 한 번에 해결하는 법은 항상 번호가 가장 빠른 학생부터 짝을 지어주면 된다.

 

(0, 1), (1, 2), (2, 3), (3, 0), (0, 2), (1, 3) -> (0, 1), (1, 2), (2, 3), (0, 3), (0, 2), (1, 3),

앞에서부터 짝을 지어주기에 <(1, 2), (0, 1)>같은 경우가 나올 수 없다.

 

구현

 

using namespace std;

int c, n, m;
bool are_friends[10][10];
bool taken[10];

//taken[i] i번째 학생이 짝을 찾은 경우 true 아니면 false
int countPairings(bool taken[10])
{
	//남은 학생 중 가장 번호가 빠른 학생을 찾는다.
	int first_free = -1;
	for (int i = 0; i < n; i++)
	{
		if (!taken[i])
		{
			first_free = i;
			break;
		}
	}

	//base case 0. 짝을 다 지어준 경우
	if (first_free == -1) return 1;

	int ret = 0;
	//학생과 짝지을 학생을 결정한다.
	for (int pair_with = first_free +1; pair_with < n; pair_with++)
	{
		if (!taken[pair_with] && are_friends[first_free][pair_with])
		{
			taken[first_free] = taken[pair_with] = true;
			ret += countPairings(taken);
			taken[first_free] = taken[pair_with] = false;
		}
	}
	return ret;
}

int main()
{
	cin >> c;
	while (c--)
	{
		cin >> n >> m;
		int y, x;

		memset(are_friends, false, sizeof(are_friends));
		memset(taken, false, sizeof(taken));

		for (int i = 0; i < m; i++)
		{
			cin >> y >> x;
			are_friends[y][x] = true;
			are_friends[x][y] = true;	//matrix form 참조
		}
		
		int cnt = countPairings(taken);
		cout << cnt << '\n';

	}
	return 0;
}

 

난도 下이지만 필자에겐 어려운 문제였다...