[알고리즘] Backtracking 이해하기

6 min readDec 29, 2018

알고리즘에서 백트래킹(Backtracking)이라는 말이 나온다. 이름만 들어서는 정확히 무엇을 말하는지 알기 어렵다. 뒤로 추척을 한다는 건가? 구글링을 해보면 ‘퇴각검색'이라는 더 아리송한 단어가 나온다. 위키피디아 정의에 따르면 아래와 같다.

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

백트래킹은 일반적인 알고리즘 중 하나이다. 마지막에 나온 말이 중요한데, CSP(Constrain Satisfaction Problems)을 해결하기 위해 쓰인다는 것이다. 백트래킹을 이해하려고 했더니 CSP를 이해해야 하는 상황이 되었다. 위키피디아 정의는 아래와 같다.

“Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations.”

한국어로 하면 ‘조건 만족 문제'인데, 일단은 넘어가고 이후에 다시 살펴보자. ‘The Algorithm Design Manual’ 책에는 백트레킹에 대해서 다음과 같이 말하고 있다.

“A technique for listing all possible solutions for a combinatorial algorithm problem.”

좀 더 이해하기 쉽다. 백트래킹은 어떤 테크닉인데 ‘조합 알고리즘 문제’에 대해 모든 가능한해를 나열하는 것이다. 그렇다. 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라' 훨씬 빠를 수 있다. 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.

구체적인 예를 들어보자. 정렬되어 있지 않은 숫자 리스트 중에 특정 숫자를 찾는 것은 n을 리스트 길이라고 했을 때, O(n) 시간 복잡도를 갖는다. 이 경우에는 백트래킹은 의미가 없다. 한 개씩 모두 살펴볼 수 밖에 없기 때문이다. 반면 N-Queen 문제의 경우는 다르다.

N * N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까?

체스를 잘 모르는 사람도 있으니 부연을 하자면, Queen은 동서남북 직진 뿐 아니라 대각선으로도 이동할 수 있다. 자 이제 어떻게 경우의 수를 셀 것인가? 가장 쉬운 방법은 모든 조합의 경우를 세는 것이다. 체스판 왼쪽부터 Queen을 차례대로 두면 상식적으로 한 컬럼에 하나의 Queen 밖에 둘 수 없다는 것을 쉽게 알 수 있다. (위아래로 움직이니깐) 다시 말하면, N * N 체스판에 N개의 Queen을 올려놓는 경우의 수를 계산해야 한다. 계산해보면,

모든 경우의 수 = 컬럼의 수 ^ 한 컬럼에 Queen을 놓는 경우의 수 = N ^ N (Power N of N)

시간 복잡도는 O(N^N)으로 엄청나게 많은 조합이 존재한다. N = 10이면 무려 100억개이다.

이제 백트래킹을 이용해보자. 한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, 성공하기 직전으로 상태를 되돌린다(back). 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.

다시, 백트래킹의 정의로 되돌아가 N-Queen 문제에 대입해보자. Queen을 최대한 많이 두는 모든 경우의 수를 찾는다. 다만, 서로를 공격하지 않아야 하므로 k번째 컬럼에 넣는 Queen을 두려면 해당 위치에서 왼쪽과 왼쪽위 대각선, 왼쪽아래 대각선에 다른 Queen들이 없어야 한다. 이 조건은 앞에서 말한 한정 조건 (CSP)이 된다. 결과적으로, 한정조건을 이용한 검색은 모든 경우의 수를 검색하는 것보다 훨씬 경우의 수가 적다.

아래 코드는 1) 모든 경우를 탐색 2) 특정 조건 명시가 포함되어 있다. 모든 경우 탐색을 위하여 DFS를 사용하였고 특정 조건은 isValid()가 처리한다.

package main
import (
   "fmt"
)
func main() {
   var N int
   fmt.Scanf("%d", &N)
   grid := make([][]bool, N)
   for i := 0; i < N; i++ {
      grid[i] = make([]bool, N)
   }
   fmt.Println(dfs(grid, 0))
}

func dfs(grid [][]bool, x int) int {
   if x == len(grid) {
      return 1
   }
   var cnt = 0
   for i := 0; i < len(grid); i++ {
      if isValid(grid, x, i) {
         grid[i][x] = true
         cnt += dfs(grid, x+1)
         grid[i][x] = false
      }
   }
   return cnt
}

func isValid(grid [][]bool, x, y int) bool {
   var diff int
   for j := x-1; j >= 0; j-- {
      diff++
      if grid[y][j] || (y-diff >= 0 && grid[y-diff][j]) || (y+diff < len(grid) && grid[y+diff][j]) {
         return false
      }
   }
   return true
}

일반화 하면 아래와 같다.

간단하게 백트래킹에 대해서 알아봤다. 조합의 숫자를 셀 때, 어떠한 조건들을 가지고 있다면, 모든 조합이 아닌 특정조건에 한정해서 조합을 카운트 할 수 있다. 검색 성능은 향상된다. 일반적으로 DFS(깊이 우선탐색)을 통하여 구현하는데 BFS(넓이 우선탐색)의 경우 상대적으로 많은 메모리가 필요하기 때문이다.

[알고리즘] Backtracking 이해하기

Written by Jeong Dowon