Backtracking

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

백트래킹의 가장 기본적인 문제인 N과 M 시리즈의 코드를 분석하면서 이해해보겠다.

#include <bits/stdc++.h> //15649 N과 M(1)
using namespace std;
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]){
            isused[i] = true;
            arr[k] = i;
            func(k+1);
            isused[i] = false;
        }
    }
}

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

arr은 답에 해당하는 여러 값을 저장하기 위한 배열이고 isused는 1 ~ N까지의 특정 숫자의 사용여부를 체크하는 배열이다.

func 함수가 백트래킹의 핵심이자 전형적인 구조이다.func함수는 현재 숫자가 k개까지 정해진 상황에서 arr[k]가 무엇인지 결정해주는 함수이다. func함수는 재귀를 이용하여 짰으니 base condition을 지정해줘야한다. 우리는 M개의 숫자를 골라야 하기 때문에 k == M일 때를 base condition으로 정한다. 이 때 M개의 숫자를 모두 고르게 됐으니 형식에 맞춰서 숫자를 출력한다. 이제 arr[k]를 결정해야한다. 먼저 1 ~ N까지의 모든 숫자를 반복해야하고 if문을 이용해 해당 숫자를 사용했으면 넘어가는 식으로 코드를 작성한다. 해당 숫자를 사용하지 않았으면 isused값을 true로 변경해주고 arr[k]의 값을 결정한다. 그 다음 재귀를 통해 k+1번째의 숫자를 결정한다. 재귀를 탈출했으면 다시 isused값을 false로 변경해줘야한다. 이전 isused값이 true인채로 다음 반복을 진행하면 해당 값(i)이 출력되지 않으므로 오류가 난다.