백트래킹

백트래킹이란 무엇인가?

-현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

(ex. 게임에서 현재상태에서 가능한 모든 선택지를 다 플레이 해보는 방법)

 

문제풀이에서 백트래킹의 활용방식은?

-각 상태별로 여러가지 경우의수가 생기고 일일이 확인할 필요가 있을때

-분기점에 다시 되돌아올 마킹을 남겨야 할때

 

Code

int n,m;
int arr[10];
bool isused[10];

void func(int k){
    if(k == m){
        for(int i=0; i<m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
        }
    
    for(int i=1; i<=n; i++){
        if(!isused[i]){
            arr[k] = i;
            isused[i] = 1;
            func(k+1);
            isused[i] = 0;
            }
        }
}

int main(void){
    ios:: sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0);
}

 

STL(순열과 조합에서 필수)

int a[3] = {1,2,3};

do{
    for(int i=0; i<3; i++)
        cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3));
/*
123
132
213
231
312
321 순열
*/

int a[4] = {0,0,1,1};
do{
    for(int i=0; i<4; i++){
        if(a[i] == 0)
            cout << i+1;
        }
        cout << '\n';
}while(next_permutation(a, a+4));
/*
12
13
14
23
24
34 조합
*/