완전탐색 경우의 수를 재귀로 수행하는 방법

그 동안 난해했던 이러한 류의 코딩하는 방법을 조금은 터득한 것 같아 정리해둘려고 한다. 

1) 항상 몇 가지 나열된 원소(숫자)를 중복을 허락하지 않고 모든 경우의 수를 구해야 할 때, 

=> n!

2) 몇 가지 나열된 원소(숫자)로 만들 수 있는 모든 경우의 수 구하기

=> n * n * n * n * ......

위와 같은 수행과정이 필요할 때 재귀적으로 코딩하는 것이 만만치 않았다. 

단지 for문을 돌면서 수행 할 수도 있다.(완전 탐색의 원소의 개수를 완벽히 알 수 있을 때 말이다.)

하지만 그렇지 않을 때에는 난 감했던 적이 많았는데 다음과 같이 코딩해주면 된다. 

이 것은 지속적으로 반복기억해주어야 겠다.

 

#include <iostream>
using namespace std;
 
int n;
int arr[4] = {1, 2, 3, 4};
bool visited[4];
int result[4];
int combination_count = 0;
 
// 4가지 수를 중복을 허락하지 않고 모든 경우의 수 구하기 => 4!
// 순열 혹은 조합? 응용 가능?
void combination(int idx){
    if (idx >= 4){
        for (int i = 0; i < 4; i++){
            cout << result[i] << " ";
        }
        cout << endl;
        combination_count++;
        return;
    }
    for (int i = 0; i < 4; i++){
        if (!visited[i]){
            result[idx] = arr[i];
            visited[i] = true;
            combination(idx + 1);
            visited[i] = false;
        }
    }
}
 
// 4가지 수로 만들 수 있는 모든 경우의 수 구하기 => 4 * 4 * 4 * 4
void recursive(int idx){
    if (idx >= 4){
        for (int i = 0; i < 4; i++){
            cout << result[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < 4; i++){
        result[idx] = arr[i];
        recursive(idx + 1);
    }
}
 
int main(){
    // recursive(0);
    combination(0);
    cout << combination_count << endl;
    return 0;
}

3) m가지의 수들로 n자리 수를 중복을 허락하여 만드는 경우

m * m * m( ... n번)

#include <iostream>
using namespace std;
 
int result[7];
bool visited[7];
int casecount = 0;
 
void make_game(int idx){
    if (idx > 6) {
        casecount++;
        for (int i = 1; i <= 6; i++){
            cout << result[i] << " ";
        }
        cout << endl;
        return; 
    }
    for (int j = 1; j <= 3; j++){
        if (!visited[idx]){
            result[idx] = j;
            visited[idx] = true;
            make_game(idx + 1);
            visited[idx] = false;
        }
    }
}
 
int main(){
    make_game(1);
    cout << casecount << endl;
    return 0;
}