#15649번 N과M(1) (c++)

#include <iostream>
#define MAX 9
int arr[MAX];
bool check[MAX];
using namespace std;

void BackTracking(int Count, int N, int M){
    if(Count==M){
        for(int i=0; i<M; i++)
            cout << arr[i] << " ";
        cout << "\n";
        return;
    }
    for(int i=1; i<=N; i++){
        if(check[i]==false){
            check[i] = true;
            arr[Count] = i;
            BackTracking(Count+1,N,M);
            check[i] = false;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int count = 0;
    int n,m = 0;
    cin >> n >> m;
    BackTracking(count,n,m);
    
    return 0;
}

백트래킹과 관련된 이론, 영상, 문제들의 예시를 몇 가지 확인하고 풀어 본 문제.

간만에 나온 재귀의 개념이 조금 헷깔리는 부분이 있어서 직접 손으로 그려가며 풀었다.

 

개인적으로 위의 코드에서 'if(Count==M)'의 'return;'만 이해하면 위의 코드는 어려운 부분이 없으리라 생각한다. 

return으로 인해 가지치기가 끝난 부분은 다시 보지 않고 다시 for문을 진행해야하는 윗 단계로 돌아가기 때문이다. 

 

역시 재귀는 이해가 안가는 부분이 생기면 직접 노가다로 구조를 그려봐야한다. 

재귀는 나올때마다 신기하고 재밋는 것 같다.