[C++]algospot PICNIC

링크 : https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: 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

 

문제 풀이

'알고리즘 문제해결 전략 책'의 6.2에 수록되어 있는 예제를 응용하여 문제 풀이를 진행했다.

해당 예제는 n개의 원소 중 m개를 고르는 모든 조합을 찾는 재귀 알고리즘으로, 다음과 같다.

// n : 전체 원수의 수, picked : 지금까지 고른 원소들의 번호, toPick : 더 골라야하는 원소의 수
void pick(int n, vector<int>& picked, int toPick) {
	// basecase
	if (toPick == 0) {
		for (int i = 0; i < picked.size(); i++) cout << picked[i] << " ";
	}

	// 고를수 있는 가장 작은 번호 계산
	int smallest = picked.empty() ? 0 : picked.back() + 1;

	// 원소 고름
	for (int next = smallest; next < n; next++) {
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

 

 

문제를 해결하기 위해 먼저

• int isFriend[45][2] : 입력받은 모든 친구 pair를 저장한 배열
• int isPair[10] : 해당 인덱스의 학생이 선택되었는지 여부를 나타냄 (0 : 선택X, 1 : 선택O)

위와 같은 두 변수를 선언했고, isFriend 배열을 순회하며 isPair가 모두 0인 경우에만 해당 친구 pair를 선택해 picked에 push했다. 이후 재귀 호출을 통해 나머지 pair들을 찾았고, 선택해야할 친구pair가 0이 될 때가 모든 학생들이 선택된 것이므로 해당 경우를 basecase로 두었다. 

 

isFriend배열의 최대 크기를 잘못 설정해 오답이 떴었는데, 이 부분을 한참동안 발견하지 못하고 시간 소비를 많이 했다. 

 

풀이 코드

// 완전 탐색
// 4ms
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int C, N, M;
int isPair[10];		// 학생이 선택되었는지 여부를 나타냄 (0 : 선택X, 1 : 선택O)
int isFriend[45][2];	// 입력받은 친구 pair들의 배열
int sum = 0;

// n : 총 친구 pair 수, picked : 지금까지 선택된 친구pair(isFriend)의 인덱스, toPick : 더 골라야 할 친구pair의 수
void pickPair(int n, vector<int>& picked, int toPick) {	
	// basecase
	if (toPick == 0) sum++;

	// 가장 작은 인덱스부터 선택
	int smallest = picked.empty() ? 0 : picked.back() + 1;

	// 친구 pair 선택
	for (int next = smallest; next < n; next++) {
		// 한 쌍의 친구pair가 모두 선택되지 않았을 경우에만 선택함
		if (isPair[isFriend[next][0]] == 0 && isPair[isFriend[next][1]] == 0) {
			isPair[isFriend[next][0]] = 1; isPair[isFriend[next][1]] = 1;
			picked.push_back(next);
			pickPair(n, picked, toPick - 1);
			isPair[isFriend[picked.back()][0]] = 0; isPair[isFriend[picked.back()][1]] = 0;
			picked.pop_back();
		}
	}
}

int main() {
	vector<int> picked;

	cin >> C; 
	for (int i = 0; i < C; i++) {
		cin >> N >> M;
		memset(isFriend, 0, sizeof(isFriend));
		memset(isPair, 0, sizeof(isPair));
		sum = 0;
		for (int j = 0; j < M; j++)
			cin >> isFriend[j][0] >> isFriend[j][1];
		pickPair(M, picked, N/2);
		cout << sum << endl;
	}
}