[C++] 알고스팟/완전탐색 - 소풍

문제 링크

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

algospot.com :: PICNIC

 

재귀 호출을 사용해서 짝이 가능해지는 경우의 수를 모두 찾아가야합니다.

이 때 짝의 순서는 상관이 없기 때문에 같은 짝의 다른 순서들을 중복으로 카운트하지 않도록 하기 위해 짝이 지어지지 않은 번호가 가장 빠른 학생부터 항상 먼저 시작해야 합니다.

 

두 번째 예제 입력의 경우 4명의 친구가 서로 다른 모든 친구와 짝이 되어도 괜찮은 경우입니다.

 

 

구현 코드

 

	#include <iostream>
	#include <cstring>
	using namespace std;
	bool areFriends[10][10];
	bool taken[10];
	int n,m;
	int countPairings(){
	int firstFree = -1;
	//남은 학생들 중 가장 번호가 빠른 학생을 찾는다
	for(int i=0;i<n;i++){
	if(!taken[i]){
	firstFree = i;
	break;
	}
	}
	//모든 학생이 짝을 찾았으면 종료
	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[firstFree] = taken[pairWith] = false;
	}
	}
	return ret;
	}
	int main(){
	int test_case;
	cin >> test_case;
	int x,y;
	while(test_case--){
	cin >> n >> m;
	for(int i=0;i<m;i++){
	cin >> x >> y;
	areFriends[x][y] = true;
	areFriends[y][x] = true;
	}
	cout << countPairings() << endl;
	for(int i=0;i<10;i++){
	memset(areFriends[i], false, sizeof(bool)*10);
	}
	}
	}

view raw picnic.cpp hosted with ❤ by GitHub