2차원 배열의 경우의 수 구하기

2 * 2 배열에 1,2를 채우는 경우의 수하기.

2 * 2 * 2 * 2 => 16가지의 경우의 수가 나와야 한다.

그런데 내가 코딩한 거에는 96가지가 나왔다. 무엇인가 잘 못 코딩해준것이었다. 

항상 2차원 배열에 대한 경우의 수 구하는 문제를 만나면 어디선가 루프를 잘 못 돌고 

그랬었는데, 확실히 내가 잘 못된 코드를 통해 풀고 있었다는 것을 깨달았다. 

2차원 루프에서 만약에 조건을 만나면 재귀 탐색 시작하고 무조건 빠져나와야 한다는 것이 중요했다.

#include <iostream>
using namespace std;
 
int arr[2][2];
int cnt = 0;
 
bool check(){
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            if (arr[i][j] == 0)
                return false;
        }
    }
    return true;
}
 
void makearr(int x_idx, int y_idx){
    for (int k = 1; k <= 2; k++){
        arr[x_idx][y_idx] = k;
 
        bool flag = false;        
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                if (arr[i][j] == 0) { 
                    makearr(i, j);
                    flag = true;        // flag를 통해 조건 만나면 반드시 빠져나오게
                    break;            // flag를 통해 조건 만나면 반드시 빠져나오게
                }
            }
            if (flag) break;    // flag를 통해 조건 만나면 반드시 빠져나오게
        }
        if (check()){
            cnt++;
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    cout << arr[i][j] << " ";
                }
                cout << endl;
            }
            cout << "--------------------------" << endl;
        }
    }
    arr[x_idx][y_idx] = 0;
}
 
int main(){
    makearr(0, 0);
    cout << cnt << endl;
    return 0;
}