[알고리즘] 완전탐색(PICNIC)

algospot.com :: PICNIC

#include <iostream>
#include <queue>
using namespace std;
queue<int> answer;

// matrix에 친구 관계, paired에 친구가 있는지 여부 저장
int matrix[10][10];
int paired[10];
int student_num, pair_num;

int makePair() {
	// 짝이 없는 학생이 있다면 idx에 저장하고, 모두 짝이 있다면 1을 반환
	int idx = -1;
	for (int i = 0; i < student_num; i++)
		if (paired[i] == -1) {
			idx = i;
			break;
		}
	if (idx == -1) return 1;

	// 짝이 없고, 친구인 학생을 찾았다면 연결시키고 재귀 호출
	int result = 0;
	for (int i = idx + 1; i < student_num; i++)
		if (paired[i] == -1 && matrix[idx][i] == 1) {
			paired[idx] = 1;
			paired[i] = 1;
			result += makePair();
			// 해당 함수가 바꾼 배열을 원래대로 되돌리며 반환
			paired[idx] = -1; 
			paired[i] = -1;
		}
	return result;
}

int main() {
	int t;
	cin >> t;
	while (t > 0) {
		cin >> student_num >> pair_num;
		for (int i = 0; i < 10; i++) {
			paired[i] = -1;
			for (int j = 0; j < 10; j++)
				matrix[i][j] = -1;
		}
		for (int i = 0; i < pair_num; i++){
			int a, b;
			cin >> a >> b;
			matrix[a][b] = 1;
			matrix[b][a] = 1;
		}
		answer.push(makePair(n));
		t--;
	}

	while (!answer.empty()) {
		cout << answer.front() << endl;
		answer.pop();
	}

	return 0;
}

예를 들어 makePair 함수 A1이 A2, A3를 차례대로 호출했다고 가정해보자.

 

​A2와 그것이 재귀호출한 함수들이 paired[]의 값을 변경했을 것이다. 하지만 여기서 paired[]가 전역변수 이므로, A2 가 값을 반환하고 A3가 호출 될 때는, A1상태에서의 paired[]가 아닌 A2 가 몽땅 뒤지며 갈아 엎은 paired[]가 있게 된다. 따라서 A2 함수가 반환하며 자신이 변경한 값을 원래대로 다시 고쳐야 함을 알 수 있다.

 

이 때 함수 코드에 "변경 >> 재귀 호출 >> 원상 복귀" 의 패턴을 넣으면, 재귀가 깊이 들어갔다 나와도 다시 알맞은 시점에서 재귀탐색을 할 수 있다.

 

​※ paired[] 을 함수의 매개변수로 전달해 구현하면 위 문제를 고려하지 않아도 될 것이다.

 

 

ruhz3/CodingTest