백 트래킹(backtracking)

제약 조건 만족 문제에서 해를 찾기 위한 전략

; 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack(다시는 이 후보군을 체크하지 않을 것을 표기)하고 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법.

실제 구현시, 고려할 수 있는 모든 경우의 수(후보군)를 상태공간트리를 통해 표현

; 각 후보군을 DFS(깊이 우선 탐색)방식으로 확인

  Promising: 해당 루트가 조건에 맞는지를 검사하는 기법

  Pruning(가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법

 

즉, 백트래킹은 트리 구조를 기반으로  DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버린다.(Pruning)

 

#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

bool isPossible(vector<int>& curQueens, int curCol)
{
    // 현재 행 = 현재 배치된 여왕 배열 크기
    int curRow = curQueens.size();    
    for(int i = 0; i < curRow; i++)
    {
        // 배치된 여왕들의 세로(가로는 놓을 수 없는 상태)와 대각선에는 놓을 수 없다
        if(curQueens[i] == curCol || abs(curQueens[i] - curCol) == curRow - i)
            return false;
    }
    return true;
}

void checkChessboard(int n, int curRow, vector<int>& curQueens, vector<int>& finalQueens)
{

    if(curRow == n)
    {
        // 여왕 배치에 성공. 첫 성공만 출력해야 하는건가?
        finalQueens = curQueens;
        return;
    }
    
    for(int i = 0; i < n; i++)
    {
        if(isPossible(curQueens, i))
        {
            // 배치가 가능한 곳에 여왕을 놓는다
            curQueens.emplace_back(i);
            // 다음 행으로 넘어가서 다시 체크(재귀)
            checkChessboard(n, curRow + 1, curQueens, finalQueens);
            // 성공이 안되는 경우는 배치된 여왕 빼기
            curQueens.pop_back();
        }
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    
    // 백트래킹, 깊이우선탐색
    
    int N = 0;
    cin >> N;
    
    int curRow = 0;             // 현재 행
    vector<int> curQueens;      // 배치된 여왕
    vector<int> finalQueens;    // 배치 완료된 여왕
    
    checkChessboard(N, curRow, curQueens, finalQueens);
    
    return 0;
}