6.3_소풍_PICNIC

문제 설명

 

algospot.com :: PICNIC

• 학생의 수(n), 친구 쌍의 수(m), 서로 친구인 두 학생의 번호(총 2 * m 개)가 주어진다.

=> 친구인 학생끼리 짝을 지어줄 수 있는 경우의 수 출력하기

 

 

문제 풀이

이 문제는 n명의 학생을 2명씩 짝짓는 조합 개수 구하기 문제이다.

그러나, 아무 조합이 가능한 것이 아니라 짝지어진 두 명이 친구관계여야 한다.

 

따라서, 짝을 지어줄 때 친구인 두 명을 짝지어주면 된다!

 

짝을 지어야 하는 아이(index)정보를 받는 재귀함수를 이용해 이 문제를 해결했다.

짝을 지어야 하는 아이와 친구관계인 아이들끼리 묶고,

그 남은 아이들끼리 다시 친구를 묶는 과정을 재귀로 반복한다.

 

그 과정에서

끝에 도달하면 성공하는 경우를 나타내는 1을 반환,

이미 index 이전의 경우에서 index와 짝이 지어진 경우라면 다음 아이를 탐색,

하는 기저 조건과 예외 조건을 추가했다.

 

문제 풀이 코드

#include <iostream>
#include <string.h>

using namespace std;

bool friends[10][10];			// [a][b] : a와 b가 친구인지 저장하는 배열
bool alreadyHaveMate[10];		// canMate에서 짝지어졌는지 상태 여부를 저장하는 배열
int C, n, m;

int canMate(int index) {
	// 끝까지 온 경우(기저조건)
	if (index == n) return 1;

	// index가 이미 짝을 찾은 경우
	if (alreadyHaveMate[index])
		return canMate(index + 1);

	// 경우의 수 세기
	int cnt = 0;

	// index 다음부터 스캔하면서 친구를 만들 수 있는지 확인
	for (int i = index + 1; i < n; ++i) {
		// i가 index와 친구이면서, 짝을 찾지 않은 경우라면
		if (friends[index][i] && !alreadyHaveMate[i]) {
			alreadyHaveMate[index] = alreadyHaveMate[i] = true;
			cnt += canMate(index + 1);
			alreadyHaveMate[index] = alreadyHaveMate[i] = false;
		}
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> C;

	for (int tc = 0; tc < C; ++tc) {
		// friends 배열 초기화
		memset(friends, false, sizeof(friends));

		// input, friends 표시
		cin >> n >> m;
		for (int i = 0; i < m; ++i) {
			int f1, f2;
			cin >> f1 >> f2;
			friends[f1][f2] = true;
			friends[f2][f1] = true;
		}

		cout << canMate(0) << endl;
	}

	return 0;
}