[ Search ] 백트래킹 (BackTracking)

BackTracking

 

 

Bruteforce는 탐색 공간을 모두 탐색하며 가능한 해를 구하는 알고리즘이었다. 우리는 이전에 연산 횟수(탐색량)를 줄이기 위해 탐색 공간을 재정의하는 등의 과정을 통해 Bruteforce의 시간복잡도를 개선하는 방법을 익혔다.

BackTracking은 Bruteforce에 첨가되는 기법과 같은 느낌으로, 탐색 공간을 조정하는 것 뿐만 아니라 탐색하지 않아도 되는 탐색 공간의 부분집합을 배제하는 과정을 통해 연산량을 줄이는 방법이다. 즉, 문제의 해가 만족하는 조건이 존재할 때, 그 조건을 만족하지 못하는 해는 미리 탐색에서 제외시킴으로써 연산량을 줄인다. 이러한 기법은 시간복잡도 개선에 유의미한 의미를 줄 수도 있고 그렇지 않을 수 있지만, 실제 프로그램의 동작이 훨씬 개선될 수 있는 방법이다. BackTracking을 이해하기 위해서는 재귀 기반의 탐색에 대한 이해가 필수적이다. 따라서 재귀 기반의 탐색 방법에 대해 짚고 넘어가고자 한다.

 

 

---

 

 

 

재귀 함수에 기반한 탐색 방법은 일반적으로 탐색 공간이 선형이 아닌 경우이다. 탐색 공간이 선형이라는 것은 Array와 같은 연속적인 구조를 의미하며, 비선형인 탐색 공간의 경우에는 그래프 등의 구조에 해당한다. 재귀 함수는 재귀 호출을 통해 자기 자신을 호출하게 되며, 호출되는 함수에서 변하는 것은 인자(Parameter)들의 값이다.

재귀 함수 f(x)가 존재한다고 했을 때, f(1)이 f(2)를 호출하고, f(2)가 f(3)을 호출하고, ...를 반복하다가 f(N)에서 함수가 종료(return)되었다고 하자. 그렇다면 f(N)이 종료되었기 때문에 f(N)을 호출했던 f(N-1)로 돌아가서 f(N-1)의 남은 연산이 진행된다. 이를 통해 알 수 있는 사실은, 재귀 호출에 기반한 탐색 방법은 깊이우선탐색(Depth-First-Search)의 성격을 지니고 있다는 것이고 실제로 DFS와 탐색 공간이 그래프인 재귀 호출 기반의 탐색 방법은 같다.

 

 

아래 그림의 그래프에서 각 노드에 존재하는 value는 각 재귀 호출의 parameter을 의미하며, 연결 관계(Edge, 간선)는 호출 관계를 의미한다고 하자. 그렇다면 해당 탐색 공간에서 탐색 순서는 다음과 같이 진행된다.

 

 

 

재귀 함수 $f$에 대해 $f(0)$이 호출되고, $f(0)$에서 $f(1)$을 호출, $f(1)$에서 $f(3)$을 호출, $f(3)$에서 $f(6)$을 호출,

$f(6)$이 return되었다면 $f(3)$으로 back, $f(3)$이 return되면 $f(1)$로 back, $f(1)$에서 $f(4)$를 호출, ...

 

 

재귀 기반의 탐색에 대해서는 타 자료를 참고하거나 해당 블로그의 Bruteforce, DFS 글을 참고하면 좋을 것이다.

 

 

 

---

 

Bruteforce 와 Backtracking

 

 

 

다시 본론으로 돌아와서, Backtracking 기법은 Bruteforce를 수행하는 과정에서 발생하는 해가 되지 않는 케이스에 대해서는 더 이상 탐색을 진행하지 않는 기법이다. 예를 들어 탐색 공간이 위 그래프와 동일하다고 가정하자. 이 때, parameter가 3인 경우에, 더 이상 탐색을 진행해도 해가 될 수 없다는 것을 알게 된다면 f(3)에서 호출되는 f(6) 또한 탐색할 필요가 없으므로 f(3)에서 탐색을 끝낸다. 다음과 같은 문제를 통해 이해해보자.

 

 

 

두 자연수 $N$과 $M$에 대해, $N$이하의 서로 다른 자연수로 이루어진 길이가 $M$인 수열을 모두 구하라.

 

 

 

예를 들어 $N$=$3$, $M$=$2$이면 $(1, 2) , (1, 3) , (2, 1), (2, 3), (3, 1), (3, 2)$가 해가 될 것이다. 이 문제를 Bruteforce 기법으로 접근해보자. 탐색 공간을 $M$차원 공간으로 설정하고, 재귀 반복을 통해 임의의 길이 M의 수열을 만든다. 이 때 M개의 수가 모두 서로 다르다면 해가 될 수 있을 것이다. 즉, 재귀 함수를 통해 길이가 M인 수열을 만들고 완성된 수열의 모든 원소가 서로 다르다면 출력하는 형태로 구현할 수 있다.

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
vector<int> v;
bool check[9];
 
void f(int x)
{
    // 길이가 M인 수열이 완성됨.
    if(x==M){
        bool flag = 0; // 같은 값이 있는지 확인
        for(int i=0; i<M; i++){
            for(int j=i+1; j<M; j++){
                if(v[i] == v[j]){
                    flag = 1;
                    break;
                }
            }
        }
        // 중복된 수가 있다면 종료
        if(flag) return;
        for(int i=0; i<M; i++) printf("%d\n", v[i]);
        printf("\n");
        return;
    }
    //[1, N]에서 임의의 수 고르기
    for(int i=1; i<=N; i++){
        v.push_back(i);
        f(x+1);
        v.pop_back();
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
    f(0);
    return 0;
}

(Code 1) : Bruteforce 기법으로 구현한 알고리즘

 

 

 

해당 코드는 길이가 M인 가능한 모든 수열을 생성하고, 그 수열의 원소가 서로 다른지 확인하여 해임을 판별하므로 매우 비효율적인 지수 시간복잡도($O(M^N · M^2)$)를 가지게 된다. 그렇다면 다음의 코드를 보자.

 

 

---

 

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
vector<int> v;
// cnt[i] : 수열에 들어 있는 i의 개수
int cnt[11];
 
void f(int x)
{
    // 가지치기 조건
    for(int i=1; i<=N; i++){
        if(cnt[i]>1) return;
    }
    //종료 조건(출력 후 종료)
    if(x==M){
        for(int i=0; i<M; i++) printf("%d ", v[i]);
        printf("\n");
        return;
    }
    //아직 고르지 않은 수 고르기
    for(int i=1; i<=N; i++){
        chk[i]++; v.push_back(i);
        f(x+1);
        chk[i]--; v.pop_back();
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
    f(0);
    return 0;
}

(Code 2) : BackTracking 기법을 이용한 알고리즘

 

 

 

현재 코드와 이전 코드의 달라진 점은 '가지치기'라고 주석 처리가 되어 있는 부분이 추가된 것, cnt Array를 사용하여 숫자를 사용한 갯수를 확인한 것이다. 이 방법으로 구현했을 때는 처음의 알고리즘보다 더욱 효율적으로 동작한다. 왜냐하면 해가 되지 않음이 자명한 경우에는 중간에 탐색을 종료해버리기 때문이다.

예를 들어 $M = 4, N = 4$라고 하자. 이 때, 탐색 과정에서 첫 번째 수로 2를 고르고, 두 번째 수로 2를 골랐다고 하면, 나머지 3, 4번째에서 나올 수 있는 탐색의 경우의 수는 16가지이다. 그런데, 이 경우에 첫 번째 수와 두 번째 수가 같으므로, 3, 4번째 수의 값에 상관없이 절대 해가 될 수 없다. 즉, 이미 처음 2개의 원소만으로 해가 될 수 없음이 판단되었기에 해당 코드에서는 조기에 탐색을 종료해버린다.( cnt[i] > 1인 조건 ) 하지만 처음에 보았던 Bruteforce 기법의 경우에는 16가지 경우를 모두 탐색하게 되므로 보다 비효율적이라고 할 수 있다.

 

 

이처럼 BackTracking은 Bruteforce 기법에서 해가 될 수 없음이 자명한 경우에 종료조건을 추가해주는 기법이다. 이름이 Backtracking인 이유는, 해가 될 수 없음을 판단하고 함수를 종료하여 다시 돌아온다는 의미를 담고 있기 때문이다. 또한 종료조건을 설정하는 것을 '가지치기'라고 하는데, 재귀 기반 탐색을 통해 나타나는 탐색 공간이 Tree 구조를 띠기 때문에 Tree에서 중간에 탐색을 종료하는 것이 가지(Branch)를 자르는 것과 같아 붙여진 이름이다.

 

 

---

 

 

 

 

Backtracking 기법을 통한 문제 해결은 결국 Bruteforce 기법과 비교 했을 때, 탐색 공간이 달라지지는 않는다. 하지만 불필요한 탐색 공간의 방문을 최소화함으로써 연산 횟수를 줄이고자 하는 목적이 존재함을 알 수 있다.

 

 

---

 

Problems

 

 

 

 

BOJ 15649 N과 M (1) : 위에서 설명한 예제로, $[1, N]$에서 중복되지 않게 $M$개의 수를 고르고, 그 수열을 모두 구하는 문제이다.

chk array를 통해 $[1, N]$의 수에 대해 각 수를 골랐는지 여부를 체크해주고, 종료 조건에 도달했을 때 수열을 출력한다. Bruteforce 기법과의 차이점은, Bruteforce 기법은 종료 조건에 도달했을 때 해가 될 수 있는지 여부를 확인한(중복되는 원소가 있는지 체크) 반면, Backtracking 기법은 중복되는 원소를 고르지 못하도록 하여 해가 될 수 없는 경우(중복된 원소가 존재)를 배제하며 탐색을 진행하는 차이가 있다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <vector>   using namespace std;   int N, M; vector<int> v; bool chk[9];   void f(int x) {     if(x==N){         for(int i=0; i<M; i++) printf("%d ", v[i]);         printf("\n");         return;     }       for(int i=1; i<=N; i++){         if(chk[i]==0){             chk[i]=1; v.push_back(i);             f(x+1);             chk[i]=0; v.pop_back();         }     } }   int main() {     scanf("%d %d", &N, &M);     f(0);     return 0; } Colored by Color Scripter

cs

 

 

 

BOJ 15650 N과 M (2) : 위 문제에서 수열이 오름차순을 유지해야 한다는 조건이 있으므로, 재귀 함수에서 인자 y를 추가한다. y는 이전에 고른 수를 저장하여, 다음에 고르는 수는 y보다 크도록 한다. 이는 반복문의 탐색 범위를 $[y+1, N]$으로 설정하여 해결할 수 있다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <vector>   using namespace std;   int N, M; vector<int> v; bool chk[9];   void f(int x, int y) {     if(x==M){         for(int i=0; i<M; i++) printf("%d ", v[i]);         printf("\n");         return;     }     //y+1부터 N까지 반복     for(int i=y+1; i<=N; i++){         if(chk[i]==0){             chk[i]=1; v.push_back(i);             f(x+1, i);             chk[i]=0; v.pop_back();         }     } }   int main() {     scanf("%d %d", &N, &M);     f(M, 0);     return 0; } Colored by Color Scripter

cs

 

 

 

 

BOJ 9663 N-Queen: 매우 유명한 Backtracking 문제로, 해결 방법이 매우 다양하다. 모든 칸을 탐색 공간으로 생각하지 않고, 각 행에 퀸을 최대 1개 놓을 수 있다는 사실을 이용해 각 행에 대해 몇 번째 열을 선택할지를 결정해주면 탐색 공간을 줄일 수 있다. 각 행에 대해 열을 선택하면 결과는 열 값을 원소로 하는 수열이 될 것이다. 종료 조건에 도달했을 때, 각각의 원소들이 대각선으로 겹치지 않는지 확인하면( 열 값을 원소로 하는 수열 ${ a_{i} }$에서 $i$≠$j$이면 $|i-j|$ ≠ $|a_{i}-a_{j}|$여야 한다. ) 해가 됨을 알 수 있다. (풀이)