백트래킹(backtracking) 기법의 이해

1. 백트래킹(Backtracking) 기법
  - 제약 조건 만족 문제에서 해를 찾기 위한 전략
    - 후보군에 제약조건을 체크하고 조건이 맞지 않으면, 그 다음 후보군으로 바로 이동하는 과정을 통해 해를 찾는 전략
      (일일이 모든 경우를 체크하지 않고, 조건에 맞지 않으면 세부검증 없이 backtracking 과정을 수행
       이해가 간다해도 말로 표현하기가 어렵다..)
  - 모든 경우의 수(후보군)는 상태공간트리(State Space Tree)로 표현한다
    - 각 후보군을 DFS 방식으로 확인
    - SST를 탐색하며, 제약조건을 체크하고 이를 만족하지 못할 경우, 다음 후보군으로 이동
      - Promising(조건체크): 해당하는 경우가 제약 조건을 만족하는지 검사하는 기법
      - Pruning(가지치기): 조건과 맞지 않으면 손절.. 다른 경우로 넘어가도록 하는 기법
 
2. 기법 사용의 예 
  - N Queen 문제: N X N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(current_row):
        if candidate[queen_row] == current_col or + \
            abs(candidate[queen_row]-current_col) == current_row-queen_row:
            return False
    return True

def DFS(N, current_row, current_candidate, final_result):
    if current_row == N:
        final_result.append(current_candidate[:]) # 얕은 복사
        return
    
    for candidate_col in range(N):
        if is_available(current_candidate, candidate_col):
            current_candidate.append(candidate_col) # 현재 가능한 후보 열 추가
            DFS(N, current_row + 1, current_candidate, final_result) # 다음 행 DFS
            current_candidate.pop()
            

def solve_n_queens(N):
    final_result = []
    DFS(N, 0, [], final_result)
    return final_result

print(solve_n_queens(4))

""" 
    [[1, 3, 0, 2], 
     [2, 0, 3, 1]] 
"""

- 출처: FASTCAMPUS