[알고리즘] 백트래킹

백트래킹 알고리즘을 우리말로 하면 '퇴각검색'이라고 할 수 있다. 그렇다면 뭐가 퇴각이라는 걸까? 이에 대한 설명은 좀 더 미뤄두도록 하자. 위키피디아의 정의를 찾아보면 아래와 같다.

“Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems…”

중요한 것은 마지막 부분인데 CSP(Constraint Satisfaction Problems)에 적용한다는 것이다. 그럼 CSP가 뭘까? 말그대로 특정 조건을 만족하도록 하는 문제를 말한다.

 

---

 

이러한 CSP의 정의를 백트래킹과 연관지어 생각해보면 백트래킹이란 "조건을 만족하는" 모든 경우의 수를 살펴보는 것이라 할 수 있다. 이러한 방식으로 실행하는 것의 이점은 무식하게 모든 경우의 수를 대입해보는 것(브루트 포스)보다 검사해봐야 할 경우의 수가 줄어든다는 것이다.(조건을 만족하는 경우에 대해서만 모든 조합을 살펴보므로)

백트래킹을 사용하는 대표적인 문제는 N-Queen이다. N-Queen문제란 NxN 체스판에 최대한 많은 수의 퀸을 서로 공격하지 않도록 두는 경우의 수를 구하는 문제이다.(참고로, 체스에서 퀸은 상하좌우, 대각선으로 움직일 수 있다.) 이 때, 당장 떠오르는 방법은 무식하게 그냥 가능한 모든 경우의 수를 다 해보는 것이다. 하지만 이는 시간복잡도가 매우 큰 연산을 수반한다.

 

---

 

그렇다면 백트래킹을 이용해보자. k번째 컬럼에 퀸을 두기 위해서는 왼쪽, 왼쪽 윗대각선, 왼쪽 아랫대각선에 퀸이 없어야 한다.(CSP) 먼저 한 컬럼에 퀸을 두었으면 오른쪽 컬럼에 가능한 자리에 퀸을 둔다. 이렇게 해서 N개의 퀸이 모두 놓이게 되면 count를 증가시킨다. 그 다음이 중요한데, 성공하기 직전의 상태로 되돌리는 것이다.(back) 예컨대, N번째 컬럼의 퀸을 들어 다른 가능한 자리에 둔다. 만약 가능한 자리가 없다면 N-1번째 컬럼의 퀸을 들어올려 다른 가능한 자리에 두고, 그 때 N번째 컬럼에 가능한 자리에 다시 퀸을 둔다. 결과적으로, 이 같은 한정조건을 이용한 조합을 탐색하게 되면 가능한 모든 경우의 수를 탐색하는 것보다 살펴봐야 할 경우의 수를 줄일 수 있다.

구현을 할 때에는 보통 DFS를 사용하여 가능한 모든 경우를 거치면서 CSP를 반영하는 특정 조건문을 이용해 해당 경우에 대해서만 연산을 수행한다.

이전에 포스팅하였던 스도쿠 문제 또한 백트래킹을 사용한 알고리즘의 예시이다. 스도쿠 문제에서는 if horizontal(nx,i) and vertical(ny,i) and bythree(nx,ny,i)이라는 CSP를 이용해 조합을 탐색하고 sdk[nx][ny]=0을 이용해서 back시켜주었다.