Backtracking

Backtracking(되추적)은 tree의 변형된 DFS라고 할 수 있다. 각 마디가 유망한지(promising) 검사하고, 만약 유망하지 않으면 그 node의 부모 node로 되추적을 하는 것을 제외하고는 DFS와 같다. 즉, 백트래킹은 유망여부를 판단하여 가지치기(Purning)를 진행함으로써 DFS 수행시 비효율적이었던 측면을 개선할 수 있는 알고리즘이다.

구현

다음은 대표적인 백트래킹 문제인 백준 9663번: N-Queen의 풀이이다.
풀이를 보면서 백트래킹 알고리즘을 이해해보자.

#include <iostream>
#define MAX 15
using namespace std;

int N, ans, board[MAX];

bool promising(int r){
    for(int i=1; i<r; i++){
        if(board[r]==board[i] || r-i == abs(board[r]-board[i])) return false; // 같은 열, 대각선에 있는 경우
    }
    return true;
}

void backtracking(int r){
    if(r==N+1){
        ans++;
        return ;
    }
    for(int c=1; c<=N; c++){
        board[r] = c; // r열 c행에 queen을 놓아봄
        if(promising(r)) backtracking(r+1); // 유망한 경우 다음 행에 퀸을 놓음
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    backtracking(1);
    cout << ans;
}