백트래킹이란?

• 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다.
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다.
• 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다.
• 해가 될 가능성이 있다면 유망하다(promising) 하다고 한다.

N-Queen 문제

N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다.

따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 없다.

N-Queen 문제는 N의 크기가 작다면 DFS 방식으로 모든 경우의 수를 탐색하면 답을 찾을 수 있다. 하지만 N의 크기가 커질 수록 탐색해야할 경우의 수가 기하급수적으로 증가한다.

아래 그림을 살펴보자.

상태 공간 트리

위 그림은 4 x 4 퀸 문제에서의 상태 공간 트리(State Space Tree)를 나타낸다.

여기서 상태 공간 트리란 모든 가능한 후보 해결법을 트리로 나타낸 것을 의미한다. 각 노드는 (행의 위치, 열의 위치)를 나타낸다.

예를 들어 (2,3) 은 2행 3열을 의미한다. 위와 같이 모든 경우의 수, 즉 퀸을 모든 위치에 배치해보는 방법은 O(N^N)이 걸린다. 매우 비효율적이다.

하지만 백트래킹을 이용하여 가지치기를 한다면 어떨까?

제일 먼저 (1,1) 에 퀸을 배치하고, 2행에서 퀸을 어디에 배치할 지 결정한다고 하자.

이 때 (2,1)은 직선상이고 (2,2)는 대각선상이라서 유망하지 않으므로(Not Promising) 해당 노드로 경로를 탐색하지 않는다(Pruning).