백트래킹(Backtracking) 알고리즘

1.백트래킹이란?

 

해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다.

 

다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다.

 

쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다.

 

경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다.

Backtracking(되추적)
해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법

 

 

 

2. DFS

 

깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로,

 

백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구현이 가능하나 여기서 다루지 않는다.)

 

부모에서 자식 노드로 깊이를 따라 들어가므로, 보통 재귀함수로 구현을 하게 된다.

 

 

Root에서 시작해 DFS로 탐색하면서 해당 경로가 해가 되지 않을 거라 판단되면,

 

해당 경로(가지)를 쳐낸다. 이를 가지치기라고 한다. 

 

이 가지치기를 얼마나 잘하는지, 즉 경로의 유망성을 얼마나 정확하고 빠르게 판단하는지가 해당 알고리즘의 효율을 결정짓는다.

 

 

Difference between BFS and DFS - GeeksforGeeks

 

 

 

3. 가지치기

 

유망성을 어떻게 판단하고, 어떤 경로로 탐색해야하는가.

 

트리를 탐색하며 갈림길을 선택할 기준을 백트래킹에선 Promising function (유망성함수) 이라 한다.

 

해당 노드의 자식노드가 유망한지 확인하고, 유망한 방향으로 골라내는 함수이다.

 

promising function으로 유망성을 확인하며 탐색하다가 유망하지 않다면 다시 부모로 돌아가 다른 경로를 탐색한다.

 

 

 

4. N-Queens 문제

 

백트래킹을 익히는데 가장 대표적인 문제로, 

 

NxN 체스에서 N개의 여왕말을 서로 잡을 수 없게 두는 방법을 찾아야한다.

 

즉 N개의 여왕이 서로가 서로의 일직선과 대각선상에 놓아지면 안된다.

 

N Queen Problem - GeeksforGeeks

 

4 x 4 체스판의 각 칸을 좌표로 생각해보자.

 

root에서 시작해 행에서 한 칸씩 말의 위치를 골라나간다 할때 그 트리는

 

와 같이 표현될 수 있다.

우리는 이 중에 유망한 경로만을 판단하며 경우의 수를 찾아가야 한다.

 

 

 

 

 이를 위한 promising function은 어떻게 될까

 

1)  일단 다른 말의 대각선 상에 위치하는지 체크해야한다

좌표의 행의 차와 열의 차가 같다면 이는 대각선 상에 위치한 것임을 인지하자.

이를 식으로 표현하면 다음과 같다.

• i번째 행의 퀸과 k번째 행의 퀸에 대해, | col(i) - col(k) | = i - k

2)  이젠 같은 열에 있는지 체크해보자

•  i번째 행의 퀸과 k번째 행의 퀸에 대해. col(i) = col(k)

 

이를 간단한 코드로 작성해보자.

bool promising(int i){
    int k = 1; // 열 번호
    bool switch = true;
    while(k < i && switch){
    	if(col[i] == col[k] || abs(col[i] - col[k]) == i - k)
    		switch = false; // 대각선 또는 같은 열 위치 ->  유망하지 않음
        k++;
    }
    return switch;
}

 

 

이제 유망성을 판단할 수 있으니 문제를 해결해보자.

 

앞서 설명처럼 모든 경로를 DFS로 도는데 그 과정에서 promising 함수로 가지치기만 하면 된다.

 

void queens(int i){
    int j;
    if(promising(i)) { // 현재 행이 유망한가 확인
    	// i = n 이면 모든 말 위치 특정했다는 의미.
    	if(i == n)
        	cout << col[1] through col[n]; // 모든 말 출력
        else
            for (j = 1; j <= n; j++){
                col[i+1] = j; // 다음 행의 각 열에 말을 두어보고 유망성 판단
                queens(i+1); // 자식, 즉 i+1행부터 탐색
            }
    }
}

 

 

 

 

 

5. 백준 9663

 

9663번: N-Queen (acmicpc.net)

9663번: N-Queen

 

 

#include<iostream>
#define MAX 15

using namespace std;

int N,cnt = 0;

int col[MAX];

bool promising(int i){
    for(int k = 0; k < i; k++){
    	if(col[i] == col[k] || abs(col[i] - col[k]) == i - k)
    		return false;
    }
    return true;
}

void queens(int i){

    if (i == N){
        cnt++;
    } else {
        for (int j = 0; j < N; j++){
            col[i] = j; // (i,j)에 여왕을 배치하고
            if(promising(i)) queens(i+1); // 유망하다면 다음행 탐색
            // 유망하지 않다면 현재 행의 여왕 위치 변경하고 다시 탐색
        }
    }

    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;

    queens(0);

    cout << cnt;

    return 0;
}

 

 

위에서 작성한 간단한 코드들을 이해했다면 이를 구현으로 옮기는건 그리 어렵지 않다.