[PICNIC] 소풍 문제

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

• (태연,제시카) (써니,티파니) (효연,유리)
• (태연,제시카) (써니,유리) (효연,티파니)

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

예제 입력

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

예제 출력

1  3  4

 

---

문제 풀이

완전 탐색을 이용해 조합을 모두 만들어 보자. 

아직 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산해라.

1. 짝을 지은 학생들의 명단 - taken

2. 친구인 학생들의 명단 - areFriends

/* 친구인 학생들 끼리 짝을 지어주기 */
/* 2019-07-08 소풍 */

#include <iostream>
using namespace std;
bool areFriends[10][10]; //학생의 수가 최대 10명이기 때문에

int findPair(int n, bool *taken) {
	//taken - 짝을 구했는가 ?
	//n - 학생 수
	int first = -1;
	for (int i = 0; i < n; i++) {
		if (!taken[i]) {
			first = i; // 가장 첫번째로 짝을 구하지 못한 사람
			break;
		}
	}
	if (first == -1) return 1; // 다 짝을 구했다면 1을 return 한다.
	int ret = 0;

	for (int i = first + 1; i < n; i++) { // 짝을 정할 사람 찾기
		if (!taken[i] && areFriends[first][i]) { //이 친구도 짝이 없고 서로 친구라면
			taken[i] = taken[first] = true; // 짝을 구함
			ret += findPair(n, taken); // 남은 짝 고르는 작업을 재귀로 떠넘긴 것. 모두 짝을 구했다면 1이 아니면 0이 return 되었을 것이다.
			taken[i] = taken[first] = false; // 다른 방법도 있을 수 있으니 다시 초기화 해준다
		}
	}
	return ret;
}

int main() {
	int c; // 테스트 케이스의 수
	int n, m; // 학생의 수, 친구 쌍의 수
	cin >> c;
	if (c > 50) return -1 ;

	for (int i = 0; i < c; i++) {
		int t1, t2;
		bool taken[10] = { false, };
		for (int i = 0; i < 10; i++)
		{
			for (int j = 0; j < 10; j++)
			{
				areFriends[i][j] = false;
			}
		}
		cin >> n >> m;
		//학생의 수는 2~10
		for (int j = 0; j < m; j++) { // 친구쌍 저장하기
			cin >> t1 >> t2;
			areFriends[t1][t2] = true;
			areFriends[t2][t1] = true;
		}
		cout << findPair(n, taken) << endl;
	}
	return 0;
}

 

 

알고리즘 문제해결 전략 1의 코드를 이용해서 풀었다. 처음엔 학생의 수에서 2개를 모든 조합을 찾는 알고리즘을 사용하려고 했으나 단순히 짝을 구하는 것이 아니라 학생들을 짝 지을 수 있는 방법의 수를 구해야 했기 때문에 책을 참고했다. 

->여기서 사용한 알고리즘도 비슷한 류임을 깨달았다.

책에서는 중복 문제를 해결하기 위해 가장 번호가 빠른 학생의 짝을 구하는 방법을 채택했고, 그렇기 때문에 findPair 함수에서는 가장 첫 번째로 짝을 구하지 못한 사람을 찾아낸다. 이때 모든 사람이 짝을 구했다면 하나의 방법을 찾은 것이기 때문에 1을 return 한다. 이 return 된 1은 추후 ret에 더해진다. 

---

처음에 0부터 짝 구하기를 시작한다.  0의 짝이 될 사람을 찾는데 자기 자신과는 친구가 될 수 없기 때문에 1부터 짝이 될 수 있는지 판별한다. 짝이 될 수 있다면 짝을 구했다고 check 한 후, 다시 나머지 학생들의 짝을 구하기 위해서 재귀로 자기 자신을 호출한다.

만약 0과 1이 짝이라고 하면 2번 친구의 짝을 찾게 될 것이다. 2번 학생의 짝이 없다면 모든 for문을 돌고 ret을 반환할 텐데 이때 ret은 0이 된다. 이는 짝짓는 것이 실패했음을 뜻한다. 하지만 2번 학생이 3번 학생과 친구라면 짝을 지을 수 있다. 이 경우에는 if문을 만족시켜 다시 재귀로 자기 자신을 호출한다. 다시 호출된 findpair 함수가 더 이상 짝을 구할 사람이 없는 것을 발견하고 1을 return 한다. 

	for (int i = first + 1; i < n; i++) { // 짝을 정할 사람 찾기
		if (!taken[i] && areFriends[first][i]) { //이 친구도 짝이 없고 서로 친구라면
			taken[i] = taken[first] = true; // 짝을 구함
			ret += findPair(n, taken); // 남은 짝 고르는 작업을 재귀로 떠넘긴 것. 모두 짝을 구했다면 1이 아니면 0이 return 되었을 것이다.
			taken[i] = taken[first] = false; // 다른 방법도 있을 수 있으니 다시 초기화 해준다
		}
	}

 

이때가 돼서야 드디어 first가 0이고 i가 1인 상황에서 ret += findPair(n, taken); 이 끝난 것이다. 

0과 1이 짝이 되는 경우뿐 아니라 0은 2,3과도 짝이 될 수 있다(0이 1,2,3과 친구라면). 이 경우를 모두 확인하기 위해서 둘 다 짝이 없다고 초기화해주고 다시 for문은 돌아가게 된다. 이런 식으로 작은 subproblem을 해결하는 재귀 함수가 모두 끝나게 되고 첫 번째로 호출된 findPair함수가 ret를 반환하면서 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 개수가 출력된다.