back tracking

백트래킹 (Back Tracking)

Posted by Jun Blog on Thursday, December 31, 2020

백트래킹

일반적으로 DFS나 BFS를 사용하여 탐색을 수행하면 모든 노드들을 탐색한다.
모든 노드를 탐색해야만하는 상황이라면 이러한 완전탐색(Full-Access) 방법을 취하는 것은 적절하다.
하지만, 모든 노드 중 특정 조건이 성립하는 노드만을 탐색하길 원한다면 DFS나 BFS는 목표하지 않은 경로도 탐색하게되므로 비효율적인 결과를 발생시킬수 있다.

백트래킹을 적용하면 유망성 검사를 통해 모든 노드를 탐색하는 것이 아닌 조건에 부합하지 않는 노드들은 배제를 시킨다. 이를 통해 완전탐색 수행시 발생하는 시간적 비효율을 획기적으로 단축시킬 수 있다.
요약하자면 백트래킹은 DFS에 유망성 검사를 결합한 가지치기 방법이라고 할 수 있다.

N-Queen

문제 : 백준 9663번 - N-Queen

백트래킹을 사용하여 해결할 수 있는 유명한 문제 중 하나인 N-Queen 문제를 통해 이해를 돕고자 한다.

N-Queen문제란 N이 주어질 때 N×N 체스판에서 N개의 퀸을 배치할 수 있는 경우의 수를 구하는 문제다.
퀸 배치시 단순히 체스판 임의의 구역에 배치하면되는 것이 아닌, 각각의 퀸이 서로를 공격할 수 없는 구역에 배치되어야 한다. 즉, 아래의 경우는 성립할 수 없는 경우이다.

우선 ‘퀸이 서로를 공격할 수 있는 구역에는 놓이면 안된다’ 라는 조건을 고려하지 않고, 4×4 체스판에서 퀸 4개를 배치할 수 있는 모든 경우를 트리로 나타내보면 아래와 같다.

  • $(1,1)$에 첫번째, $(2,1)$에 두번째, $(3,1)$에 세번째, $(4,1)$에 네번째 퀸을 배치
  • $(1,1)$에 첫번째, $(2,1)$에 두번째, $(3,1)$에 세번째, $(4,2)$에 네번째 퀸을 배치
    …

이제 ‘퀸이 서로를 공격할 수 있는 구역에는 놓이면 안된다’ 라는 조건(유망성 검사)을 적용하여 트리의 시작점에서부터 탐색을 시작해보자.

  • 첫번째 퀸을 $(1,1)$에 배치

    • 두번째 퀸을 $(2,1)$에 배치 가능한가? 아니오.
    • 두번째 퀸을 $(2,2)$에 배치 가능한가? 아니오.
    • 두번째 퀸을 $(2,3)$에 배치 가능한가? 예.

  • 두번째 퀸을 $(2,3)$에 배치

    • 세번째 퀸을 $(3,1)$에 배치 가능한가? 아니오.
    • 세번째 퀸을 $(3,2)$에 배치 가능한가? 아니오.
    • 세번째 퀸을 $(3,3)$에 배치 가능한가? 아니오.
    • 세번째 퀸을 $(3,4)$에 배치 가능한가? 아니오.

    세번째 퀸이 놓일 수 있는 구역이 없다.
    즉, $(2,3)$은 유망하지 못하므로 되추적을 진행하여 이전단계인 $(1,1)$에 첫번째 퀸을 배치하는 경우로 돌아간다.

  • 첫번째 퀸을 $(1,1)$에 배치

    • 두번째 퀸을 $(2,4)$에 배치 가능한가? 예.

  • 두번째 퀸을 $(2,4)$에 배치

    • 세번째 퀸을 $(3,1)$에 배치 가능한가? 아니오.
    • 세번째 퀸을 $(3,2)$에 배치 가능한가? 예.

  • 세번째 퀸을 $(3,2)$에 배치

    • 네번째 퀸을 $(4,1)$에 배치 가능한가? 아니오.
    • 네번째 퀸을 $(4,2)$에 배치 가능한가? 아니오.
    • 네번째 퀸을 $(4,3)$에 배치 가능한가? 아니오.
    • 네번째 퀸을 $(4,4)$에 배치 가능한가? 아니오.

    네번째 퀸이 놓일 수 있는 구역이 없다.
    $(3,4)$에 세번째 퀸을 배치하는 경우는 유망하지 못하므로 되추적을 진행하여 이전 단계로 돌아간다.

  • 두번째 퀸을 $(2,4)$에 배치

    • 세번째 퀸을 $(3,3)$에 배치 가능한가? 아니오.
    • 세번째 퀸을 $(3,4)$에 배치 가능한가? 아니오.

네번째 퀸을 배치할 수 있는 구역이 존재하지 않는다.
따라서 $(1,1)$에 첫번째 퀸을 배치하는 경우는 유망하지 못하다는 결론이 나오며 $(1,2)$부터 탐색을 이어나간다.

이후의 과정들은 위와 유사한 동작들이 반복되어 수행되기에 지면이 길어지므로 생략한다.

최종 정답의 도출 여부를 떠나 첫번째 퀸이 $(1,1)$ 위치에 유망한가 여부에 대해서만 놓고 봤을 때,
‘유망하지 않다.’ 라는 답을 도출하기까지 13번(1 + 4 + 4 + 4)의 노드 방문이 이루어졌다. 백트래킹을 수행하지 않고 DFS를 진행했을 때는 85(1 + 4 + 16 + 64)번의 노드를 방문해야하므로 백트래킹을 적용하면 수행시간의 효율이 향상된다는 것을 알 수 있다.

Code

백준에서 AC를 받은 코드를 첨부한다.

#include <iostream>
#include <vector>
#define MAX 16;
using namespace std;

int n, ans = 0;
vector<int> col;

//유망한 위치인가?
bool possible(int cur){
    for(int i=1; i < cur; i++){
        //가로 세로 검사
        if(col[i] == col[cur]) return false;

        //대각 검사
        if(abs(cur - i) == abs(col[cur] - col[i])) return false;
    }
    return true;
}

void dfs(int row){
    if(row > n){
        ans++;
        return;
    }

    for(int i=1; i<=n; i++){
        col[row] = i;

        if(possible(row)){
            dfs(row + 1);
        }
        else{
            col[row] = 0;
        }
    }
}

int main() {
    cin >> n;
    col.resize(n+1);

    for(int i=1; i<=n; i++){
        col[1] = i; //1,i부터 시작
        dfs(2);
    }

    cout << ans;
}
CATALOG