Backtracking - Queen Problem

백트래킹(Backtracking)은 문제에서 주어지는 한정된 조건을 만족하는 해를 구할 때 사용하는 알고리즘이다.

문제에서 가능한 모든 해 집합을 대입하면, 당연히 만족하는 해를 찾을 수 있다. 여기서, 백트래킹을 이용하면 시간을 크게 단축시킬 수 있다. 쉽게 말하자면 다음과 같다:

노드의 유망성을 확인한 후, 유망하지 않으면 그 노드의 부모 노드로 돌아간다. 즉, 유망하지 않은 노드는 배제한다.

노드가 ‘유망하다’는 것은 문제의 조건을 (아직까지는) 만족한다는 뜻이다. 이러한 논리를 가장 쉽게 이해할 수 있는 대표적인 문제는 Queen Problem이다.

Queen Problem은 N*N 체스판에 N개의 Queen을 놓는데, 각각의 Queen이 서로를 위협시키지 않도록 위치시키는 문제이다. 위와 같이 N개의 Queen을 놓을 수 있는 방법의 수를 구해야 한다고 하자. 백트래킹을 사용하여 다음과 같이 문제를 해결할 수 있다.

우선, 각 행에 한 개의 Queen이 있어야 한다는 점은 명백하다. 따라서, 우리는 체스판을 1차원 배열로 표현할 것이다. 배열 chess[N]을 놓고, i 행 j 열에 Queen이 놓인다면 chess[i] = j 와 같이 표현한다. 이렇게 놓음과 동시에 우리는 한 행에 두 개의 Queen이 놓이는 경우를 모두 제외하였다. 남은 두 조건은 같은 열과 대각선에 Queen이 놓이지 않는 것이다. 같은 열에 놓이지 않는 것은 모든 a, b에 대해 chess[a] != chess[b] 이면 되며, 같은 대각선에 놓이지 않는 것은 i와 j의 차를 이용하여 구할 수 있다. (chess[i]와 chess[j]의 차와, i와 j의 차가 달라야 한다!)

이제 문제의 조건을 모두 (코드로) 구현하였다. 남은 것은 모든 해집합에서 위 조건을 모두 만족시키는 경우를 모두 찾는 것이다. 여기서 백트래킹을 사용한다.

첫 번째 행(chess[0])부터 시작하여, i 번째행을 i번째 깊이로 생각한다. chess[0]의 값을 정한다. chess[0] = 0 이 된 첫 번째 상황을 생각하자. Queen을 처음 한 개 놓았으므로 어긋나는 조건이 없다. 다음, chess[1]의 값을 정한다. chess[1] = 0 이라면, 조건에 어긋난다. ( 한 열에 두 개의 Queen이 놓임) 따라서 chess[1] = 0 인 노드는 “유망하지 않은 노드”가 되는 것이다. 이미 조건을 만족시키지 못하기 때문이다. 이 경우 백트래킹을 통해, 아래의 노드들은 확인할 필요도 없이 다음 노드로 넘어간다. chess[1] = 1 인 경우이다. 이 경우도 조건을 만족하지 않으므로 (대각선에 두 개의 Queen이 놓임), chess[1] = 2 인 경우로 바로 넘어간다. 이 노드는 조건을 만족하는 “유망한 노드”이다. 따라서 다음 level로 넘어가 chess[2] 의 값을 정해준다….

위와 같은 방법으로 ‘노드의 유망성’을 판단하여 유망하지 않다면 바로 스킵하는 전략이 백트래킹이다. 모든 경우의 수를 확인하는 DFS와 비해 시간이 훨씬 절약되는 것을 느낄 수 있을 것이다.

완성된 코드는 여기 에서 확인할 수 있다. (백준 9663)