[알고리즘 문제해결 전략] 소풍

문제출처

• [알고리즘 문제해결 전략1] - 6장 완전탐색 예제
• 소스코드는 구현한 함수의 동작 여부를 관찰하기 위해 본인의 테스트 코드를 추가하여 작성한 결과이다.

문제 설명

• 학생들의 쌍에 대해 친구 여부가 주어지고, 서로 친구인 학생들만 짝을 할 수 있음
• 전체 인원에 대해 짝을 지을 수 있는 모든 경우의 수를 계산하기

문제 접근 방향 (Solution)

• 조합을 구하는 문제와 유사하다는 생각이 든다.
• 앞 번호 학생부터 짝을 만들어주는데 본인보다 앞 번호의 학생은 짝을 만드는 대상으로 생각하면 안된다. 왜냐하면, (0,1)과 (1,0)은 서로 같은 경우를 의미하기 때문에 중복으로 셀 수 있기 때문이다.

구현 결과

#include <iostream>
#include <memory.h>
using namespace std;

int n;
bool areFriends[10][10] = { false, };

// Test Case마다 초기화
void init()
{
	n = 0;
	memset(areFriends, false, sizeof(areFriends));
}

int countPairings(bool taken[10])
{
	int firstFree = -1;
	for (int i = 0; i < n; i++) // 앞에서부터 짝이 없는 학생 찾기
	{
		if (!taken[i]) {
			firstFree = i;
			break;
		}
	}
	// 기저 사례: 모든 학생이 짝을 찾았으면 경우의 수 1 추가 및 탐색 종료
	if (firstFree == -1) return 1;
	int ret = 0;
	// firstFree 학생과 짝을 지을 학생을 찾는다.
	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; // 모든 학생이 짝을 이룰 수는 없는 경우
}

int main()
{
	int C;
	cin >> C;
	for (int test_case = 0; test_case < C; test_case++)
	{
		init();
		int m;
		cin >> n >> m;
		for (int i = 0; i < m; i++)
		{
			int friend1, friend2;
			cin >> friend1 >> friend2;
			areFriends[friend1][friend2] = true;
			areFriends[friend2][friend1] = true;
		}
		bool taken[10] = { false, };
		int ans = countPairings(taken);
		cout << ans << endl;
	}
	return 0;

}

Test Case

3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5