[알고리즘] '재귀 호출'과 '완전 탐색'으로 문제를 해결하는 방법, 재귀 호출 문제

완전 탐색으로 문제를 해결하기 위해 필요한 과정

 

1. 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.

 

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.

- 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.

 

3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.

 

4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 기저 사례로 처리한다.

 

 

문제 : 소풍 (문제 ID : PICNIC, 난이도 : 하)

유치원 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 한다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 한다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 계산하는 프로그램을 작성하라. 짝이 되는 학생들이 일부만 다르더라고 다른 방법이라고 본다.

 

예를 들어 다음 두 가지 방법은 서로 다른 방법이다.

 

- (태연, 제시카) (써니, 티파니) (효연, 유리)

- (태연, 제시카) (써니, 유리) (효연, 티파니)

 

시간 및 메모리 제한

프로그램은 1초 내에 실행되어야 하고, 64MB 이하의 메모리만을 사용해야 한다.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 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

 

풀이

- isFriend[i][j] : i와 j가 친구라면 true, 친구가 아니면 false 값을 가짐

- isPair[i] : i번 친구가 짝이 있으면 true, 짝이 없으면 false 값을 가짐

- 하나의 짝을 만드는 것을 한 조각으로 생각하고 함수를 작성한다. 먼저 짝이 없는 친구를 찾아 번호를 저장한 후, 모두 짝이 있다면 1을 반환한다. 짝이 없는 다른 친구와 짝을 맺고, 다음 짝을 찾는 함수를 재귀로 호출한다. 이를 짝이 없는 다른 친구에 대해 모두 실행하여 count 변수에 경우의 수를 저장하여 값을 도출한다.

 

코드

#include <iostream>
using namespace std;
bool isFriend[10][10] = { {false, } };
int n;

int countPairing(bool isPair[10]) {
	// 기저 사례 - 짝이 없는 친구를 찾는다. 다 짝이 있다면 -1
	int firstFree = -1;
	for (int i = 0; i < n; i++) {
		if (!isPair[i]) {
			firstFree = i;
			break;
		}
	}
	if (firstFree == -1)
		return 1;
	// 재귀호출 - 가능한 짝을 만들어 그 다음 짝을 만드는 것을 다음 조각으로 만든다.
	int count = 0;
	for (int i = firstFree + 1; i < n; i++) {
		if (!isPair[i] && isFriend[firstFree][i]) {
			isPair[firstFree] = isPair[i] = true;
			count += countPairing(isPair);
			isPair[firstFree] = isPair[i] = false;
		}
	}
	return count;
}

int main() {

	int answer[50];
	bool isPair[10] = { false, };
	int C;
	cin >> C;

	for(int i=0;i<C;i++){
		// 학생의 수, 친구 쌍의 수 입력
		int m;
		cin >> n >> m;

		for (int i = 0; i < m; i++) {
			int f1, f2;
			cin >> f1 >> f2;
			isFriend[f1][f2] = isFriend[f2][f1] = true;
		}
		
		answer[i] = countPairing(isPair);
	}

	for (int i = 0; i < C; i++)
		cout << answer[i] << endl;

	return 0;
}

 

문제 : 게임판 덮기 (문제 ID : BOARDCOVER, 난이도 : 하)

작성 중