백트래킹 (Backtracking)

백트래킹이란?

백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보를 탐색하여 정답을 찾도록 하는 알고리즘을 말한다.

이때 일반적인 브루트포스(Brute Force) 알고리즘과 백트래킹의 차이점은, “정답을 찾는 도중 정답이 될 가능성이 없는 경우, 그 즉시 되돌아가 다른 경로를 탐색하여 답을 찾는다”는 것이다.

 

백트래킹이 작동되는 방식은 크게 다음과 같다:

1. 현재 상태에서 가능한 후보 중 하나를 고른다.
2. 해당 후보에서 재귀적으로 다음 단계를 탐색해 나간다.
   1. 탐색하는 중, 정답이 될 수 없는 경우 탐색을 종료한다.
   2. 주어진 조건을 모두 만족하는 경로인 경우, 해당 경로를 정답으로 처리한다.
3. 탐색이 끝나면, 상태를 원래대로 되돌린 후, 다른 후보를 골라 반복한다.

출처: https://www.geeksforgeeks.org/dsa/n-queen-problem-backtracking-3

문제를 풀기 위해서 위와 같은 상태 공간 트리(State Space Tree)를 사용할 수 있다. 위 그림처럼, 매 상태에서 조건에 맞는지 여부를 파악하고, 조건을 만족하지 않는다면 이후 경로를 더 이상 탐색하지 않고, 이전 상태로 돌아간 뒤 다음 후보를 찾아 탐색을 진행한다.

상태 공간 트리
문제 해결과정에서 각각의 중간 상태 하나를 한 개의 Node로 표현하여 나타낸 트리

이렇게 가능성이 없는 경로를 배제하는 방법을 가지치기(Pruning)이라고 하며, 가지치기가 일어나는 시점 아래의 모든 Subtree에 대한 탐색을 건너뛰고 다음 경로를 탐색할 수 있도록 한다. 이를 통해 브루트포스보다 더 효율적으로 정답을 찾아갈 수 있다.

 

일반적으로 백트래킹은 재귀함수를 이용한 DFS 방식으로 구현하게 된다. BFS를 잘 안쓰는 이유는, 모든 경우의 수를 고려하기 위해서는 Queue의 크기가 매우 커질 수 있기 때문이다.

 

N-Queen

백트래킹 문제 중, 제일 유명한 문제인 N-Queen 문제를 풀어보자. 유명한 만큼, 여러 코딩테스트 사이트에서 쉽게 찾아볼 수 있는 문제이다. (백준, 프로그래머스, LeetCode)

 

우리는 가로와 세로 길이가 모두 N인 체스판에서 N개의 Queen이 서로를 공격하지 못하도록 배치할 수 있는 경우의 수를 찾아보도록 하자.

N-Queen 문제의 상태 공간 트리

 

2개의 Queen은 서로 같은 행에 존재할 수 없으므로, 모든 N개의 행 각각에는 Queen이 1개씩만 존재해야 한다. 즉, 가능한 열 위치의 조합을 확인하면 풀 수 있다.

 

구체적으로 문제 해설을 하지는 않지만, 백트래킹을 이용해서 Python으로 구현한 정답은 아래와 같다.

cols = [False] * N
left_diag = [False] * (N*2) # 오른쪽 아래에서 왼쪽 위로, row+col 값 동일
right_diag = [False] * (N*2) # 왼쪽 아래에서 오른쪽 위로, row-col 값 동일

def dfs(N, cur_row):
    if N==cur_row:
        return 1

    cnt = 0
    for col in range(N):
        if not cols[col] and not left_diag[cur_row+col] and not right_diag[cur_row-col]:
            cols[col] = True
            left_diag[cur_row+col] = True
            right_diag[cur_row-col] = True

            cnt += dfs(N, cur_row+1)

            cols[col] = False
            left_diag[cur_row+col] = False
            right_diag[cur_row-col] = False

    return cnt

 

References

• 바킹독의 실전 알고리즘 0x0C강: 백트래킹
• https://velog.io/@gayeong39/백트래킹-알고리즘-BackTracking
• https://en.wikipedia.org/wiki/Backtracking