[Algorithm] 백트래킹(Backtracking)

백트래킹이란 ?

백트래킹은 모든 경우의 수를 고려하는 알고리즘을 의미합니다. 트리 형태의 상태공간이 있을 때, DFS와 같은 완전탐색 알고리즘을 사용하여 모든 지점을 탐색하게 됩니다. DFS는 현재 지점에서 방문할 곳이 있으면 재귀를 호출하여 계속해서 이동하는 특징이 있습니다. 하지만, DFS는 모든 곳을 방문하기 때문에 비효율적인 측면이 있습니다. 따라서 목표지점이 될 가능성이 있는지를 검사한 후 그 지점들만 방문하는 것을 백트래킹 알고리즘이라 합니다. 즉, 백트래킹은 DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 효율적으로 찾는 알고리즘 입니다.

 

백트래킹과 DFS의 차이점?

백트래킹과 DFS의 차이점을 많이 헷갈려하시는데,

DFS는 연결되어있는 모든 노드들을 깊이 우선순위에 따라 탐색하는 알고리즘입니다. 

백트래킹은 DFS를 사용하여 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 배제(가지치기)하는 특징을 가집니다. 

 

 

다음으로 대표적인 예제인 N-Queens 문제를 살펴봅시다. 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다. 

Queen들이 서로 공격하는 조건은 다음과 같습니다. 

• 같은 행에 위치
• 같은 열에 위치
• 대각선에 위치

같은 행에 위치하면 공격한다는 조건을 고려하여 볼 때, 한 행에 퀸은 한개만 존재한다는 것을 알 수 있습니다. 따라서 이차원배열이 아니라 일차원배열로 퀸의 위치를 나타내어도 상관이 없습니다. 예를 들어, row[2]=3; 은 2행 3열에 퀸이 존재한다는 의미입니다. 

 

//
//  Copyright (c) 2021 HyeJin Shin All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
int ans=0;
int row[16];
bool check(int x) {  //유망성 체크
    for(int i=0;i<x;i++){
        if (row[i]==row[x]||abs(i-x)==abs(row[i]-row[x])) {return false;}  //같은 열이거나 대각선인 경우 return false (같은 행은 올 수가 없음)
    }
    return true;
}
void nqueen(int x){
    if(x==n){ //하나의 경우의 수 충족
        ans++;
        return;  //이전 노드로 돌아감
    }
    else {
        for(int i=0;i<n;i++){
            row[x]=i;
            if(check(x)){  //유망성을 체크한 뒤
                nqueen(x+1);  //그 다음 행 탐색
            }
        }
    }
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    nqueen(0);
    cout<<ans;
    
}

더 자세한 설명이궁금하다면 아래 링크를 참고해주세요.

https://toki0411.tistory.com/11

[백준, c++] 9663 N-Queen