알고스팟 : 소풍

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

문제 읽기

n은 친구 수, m은 쌍의 수

코드 6.4의 문제는 중복된 요소들도 같이 센 다는 것이다. 따라서 사전순으로 나열하여 경우의 수를 세보도록 하자.

int n;
bool areFriends[10][10]; //배열을 사용하여 서로가 서로와 친구인 것을 체크하기
			 //(1, 0)가 TRUE라면 (0, 1)도 당연히 TRUE
int countPairings(bool taken[10]) {
	int ret;
	int firstFree = -1; //남은 학생들 중 가장 번호가 빠른 학생을 찾는다
	for (int i = 0; i < n; i++) {
		if (!taken[i]) { //계산된 것이 아니라면
			firstFree = i;
			break;
		}
	}
	if (firstFree == -1) return 1; //모든 학생들이 짝을 찾았다면 과정을 종료
	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;
}

여기서 이제 이해가 안되는 부분이 다음 부분이다.

taken[firstFree] = taken[pairwith] = true;
ret += countPairings(taken);
taken[firstFree] = taken[pairwith] = false;

firstFree 다음 애를 시작으로 계산을 시작한다.
사전순으로 접근하기로 했으니까. pairwith는 taken는 체크되어있지 않는 상태여야하고 계산에 들어왔다면 체크한다. 그래야 재귀를 거치면서 중복으로 선택하는 것을 막을 수 있기 때문이다. 예를 들어 이미 (0, 1)을 선택했는데 다음 재귀 단계에서 (1, 2)를 선택하는 것을 막는 것이다.
그 계산이 끝나면 false로 체크를 풀어준다. 어차피 다 계산이 되었으므로 풀어주는 것이 다음 연산을 위해 좋다.

그렇다면 내가 다시 n과 m을 받으면서 false로 초기화하지 않아도 된다는 소리다!

코드

#include <iostream>
using namespace std;

int n;
bool areFriends[10][10]; 
bool taken[10]{ false };

int countPairings(bool taken[10]) {
	int ret = 0;
	int firstFree = -1; //남은 학생들 중 가장 번호가 빠른 학생을 찾는다
	for (int i = 0; i < n; i++) {
		if (!taken[i]) { //계산된 것이 아니라면
			firstFree = i;
			break;
		}
	}
	if (firstFree == -1) return 1; //모든 학생들이 짝을 찾았다면 과정을 종료
	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;
}

void check(int m) {
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		areFriends[a][b] = areFriends[b][a] = true;
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testcase, m, ans;
	cin >> testcase;
	for (int i = 0; i < testcase; i++) {
		cin >> n >> m; //n은 친구 수, m은 쌍의 수
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				areFriends[i][j] = false;
			} //taken[i] = false; //문제읽기에서 지운 이유 서술
		}
		check(m);
		ans = countPairings(taken);
		cout << ans << endl;
	}
}

분석

2차원 배열 bool을 &을 이용해 인자로 받아오는 방법을 몰라서 밖에서 선언하고 매번 false로 초기화했다...

책에서 처럼 재귀를 이용해 countPairings를 계산하였고 나머지는 크게 문제 없었던 것 같다.