백트래킹.md

백트래킹 BackTracking

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

BackTracking vs DFS

백트래킹(Backtracking)

해를 찾아가는 도중, 지금의 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)으로 돌아가(Backtracking) 다음 자식 노드로 이동한다. 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)라고 한다.

깊이 우선 탐색(DFS)

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

대표 문제 : N Queens

class Solution:
    def solveNQueens(self, n):
        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):
        str_list = ['.'] * self.n
        str_list[col] = 'Q'
        return ''.join(str_list)
    
    def bt(self, row, col, board):
        # 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()

대표 문제 : 순열 Permutations

1. Recursion

def permute(arr, r):
    arr.sort()
    used = [False] * len(arr)
    output = []
    
    def generate(chosen, used):
        if len(chosen) == r:
            output.append(chosen[:])
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = True
                generate(chosen, used)
                used[i] = False
                chosen.pop()

    generate([], used)
    return output

2. Swap

def permute(arr, r):
    arr.sort()
    output = []
    
    def generate(level):
        if level == r:
            output.append(arr[:r])
            return
        for i in range(level, len(arr)):
            arr[i], arr[level] = arr[level], arr[i]
            generate(level+1)
            arr[i], arr[level] = arr[level], arr[i]
            
    generate(0)
    return output

대표 문제 : 조합 Combinations

def combine(arr, r):
    arr.sort()
    used = [False] * len(arr)
    output = []
    
    def generate(level, chosen, used):
        if len(chosen) == r:
            output.append(chosen[:])
            return
        for i in range(level, len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = True
                generate(i+1, chosen, used)
                used[i] = False
                chosen.pop()
        
    generate(0, [], used)
    return output

📗 참고

• N-Queens - LeetCode
• Permutations - LeetCode
• Combinations - LeetCode