[Algorithm] 백트래킹(BackTracking)

백트래킹(BackTracking)은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다.

 

BackTracking vs Dynamic Programming

백트래킹과 동적 계획법은 재귀를 통해 문제를 해결한다는 공통점이 있지만, 근본적인 차이점을 가지고 있다.

백트래킹(Backtracking)

백트래킹은 현재 상태에서 가능한 모든 후보군(Decision Space)를 하나씩 살펴가면서 해가 될 가능성이 있으면 후보를 구축하고, 해가 될 가능성이 없다면 즉시 후보를 포기하면서 해를 찾아나가는 방식이다. 이때, 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)라고 한다.

동적 계획법(Dynamic Programming)

동적 계획법은 큰 문제를 작은 문제로 나눌 수 있고 (Problem -> Subproblems), 이러한 Subproblem들이 반복될 때 Memoization 기법을 통해 연산 수를 줄여 문제를 해결하는 패러다임이다. 즉, 동적 계획법의 핵심은 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 것에 있다.

 

BackTracking vs DFS

백트래킹(Backtracking)

백트래킹은 해를 찾아가는 도중, 지금의 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)으로 돌아가(Backtracking) 다음 자식 노드로 이동한다.

깊이 우선 탐색(DFS)

DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄일 수 없다.

 

 

대표문제 : N-Queens

문제 설명

크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경우의 수를 구하는 문제이다. 

문제 풀이

해당 문제는 백트래킹의 대표적인 문제이다. 아래 그림처럼 N x N 체스판에 N 개의 퀸을 놓는 경우를 재귀적으로 살펴가며 유망한지 확인하면 된다.

해당 문제의 유망 조건은 아래와 같다.

1. 같은 행에 이미 위치한 퀸이 없어야 한다.
2. 같은 열에 이미 위치한 퀸이 없어야 한다.
3. 대각선에 이미 위치한 퀸이 없어야 한다.

위 그림과 같이 백트래킹을 진행할 경우, 재귀의 깊이는 N x N이 되고, 매 재귀 단계의 Decision Space도 N x N이 된다. 즉, N=4일 때 해당 문제의 시간복잡도는 16^16이 되는 것이다. 하지만 위 유망 조건의 1번을 이용하면 아래 그림과 같이 재귀의 깊이와 Decision Space를 N으로 줄일 수 있다. 하나의 행에 하나의 퀸만 올 수 있기 때문에 N번의 재귀만 실행하면 되고(재귀 깊이를 행번호로 생각), 각 재귀마다 N개의 열만을 후보로 탐색하면 된다. 이를 통해 16^16의 시간복잡도를 4^4로 줄일 수 있다.

구현 코드

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.results = []
        self.col_set = set() # col
        self.diag_set1 = set() # row-col
        self.diag_set2 = set() # row+col
        self.n = n # length
        
        for x in range(n):
            self.bt(0, x, [])
        
        return self.results
    
    def create_str_row(self, col:int) -> str:
        str_list = ['.'] * self.n
        str_list[col] = 'Q'
        return ''.join(str_list)
    
    def bt(self, row:int, col:int, board:List[str]):
        # exit conditions
        if row==self.n or col==self.n:
            return
        if col in self.col_set:
            return
        diag1_info = row-col
        diag2_info = row+col
        if diag1_info in self.diag_set1:
            return
        if diag2_info in self.diag_set2:
            return
        
        # process
        str_line = self.create_str_row(col)
        board.append(str_line)
    
        if len(board) == self.n:
            self.results.append(board.copy())
            board.pop()
            return
        
        # duplicates sets
        self.col_set.add(col)
        self.diag_set1.add(diag1_info)
        self.diag_set2.add(diag2_info)
        
        # recursive calls
        for x in range(self.n):
            self.bt(row+1, x, board)
        
        # duplicates sets pop
        self.diag_set2.remove(diag2_info)
        self.diag_set1.remove(diag1_info)
        self.col_set.remove(col)
        board.pop()