B_

1. 소개

백트래킹(Backtracking) 알고리즘은 주어진 문제에 대한 모든 경우를 탐색하여 문제를 해결하는 알고리즘이다. Backtracking이란 말에서 탐색 도중 조건을 만족하지 않는 상태에 도달하는 경우 이전 상태(Back)로 되돌려 준다. 예를 들어 다음과 같은 문제를 생각해볼 수 있다.

8*8 체스판에 Queen 8개가 서로를 공격하지 못하도록 놓는 방법은 무엇인가?

문제에 대한 해답을 찾는 가장 간단한 방법은 Queen 8개를 놓는 모든 방법에 대해 서로 공격할 수 있는 Queen이 있는지 검사하는 것이다. 이 경우 시간복잡도는 $O(N^N)$이 된다.

이 문제를 백트래킹을 사용하여 탐색하는 경우, Queen을 하나씩 놓으면서 현재 놓는 Queen을 공격할 수 있는 또 다른 Queen이 있는 경우 더 이상 탐색하지 않고 이전 상황으로 되돌려준다. 이 방법을 사용하면 더 적은 경우에 대한 탐색을 진행하므로 시간복잡도를 줄일 수 있다.

2. 가지치기

백트래킹 알고리즘을 사용한 프로그램의 시간복잡도를 줄이기 위해 가지치기를 잘 활용해야 하는 경우가 많다. 가지치기란, 백트래킹에서 조건에 따라 탐색할 필요 없는 경우들을 잘 쳐내어 쓸데없는 탐색 시간을 줄이는 방법이다.

가지치기를 잘 하면 쓸데없는 경우를 탐색하느라 시간을 낭비할 필요가 없어 백트래킹 알고리즘의 시간복잡도를 줄일 수 있지만, 가지치기를 충분히 하지 않은 백트래킹 알고리즘을 사용하면 시간복잡도가 너무 커서 문제에서 요구하는 시간 안에 돌아가지 않을 수 있다.

다음은 N-Queen 문제에 대한 기본적인 가지치기 방법이다.

• 이전에 Queen을 놓은 열 / 행에는 Queen을 놓을 수 없다
• 이전에 Queen을 놓은 대각선에는 Queen을 놓을 수 없다. 즉 이전에 놓은 Queen과 (x좌표값 + y좌표값)이 같거나 (x좌표값 - y좌표값)이 같은 곳에는 새로운 Queen을 놓을 수 없다.