[코딩 + 알고리즘 완주반] 24일차. 백트래킹

# 백트래킹

- 제약조건만족 문제에서 해를 찾기 위한 전략

- 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법

- 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현

- 각 후보군을 DFS 방식으로 확인

- Promising : 해당 루트가 조건에 맞는지 검사하는 기법

- Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법

 

# N-Queen 문제

N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

퀸 :  수직, 수평, 대각선 이동 가능

Pruning(가지치기) for N Queen 문제

 - 한 행에는 하나의 퀸밖에 위치할 수 없음 ( 수평이동가능하므로)

 - 맨 위 행부터 배치하고 다음행에 해당 퀸이 이동할 수 없는 위치를 찾아 퀸을 위치

 - 앞선 행에 배치한 퀸으로 인해 다음 행에 가능한 위치가 없을 경우에는 더이상 퀸을 배치하지 않고 이전 행의 퀸의 위치를 바꿈

     - 가능한 경우의 수를 상태 공간 트리 형태로 만든 후 DFS 방식으로 접근

 

Promising for N Queen 문제

 - 해당 루트가 조건에 맞는지 검사하는 기법

이전 행의 퀸의 위치와 비교 

 - 수직 체크 : 열번호의 차이가 0 이면 수직 

 - 대각선 체크: 행번호의 차이와 열번호의 차이가 같으면 대각선

 

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)
            current_candidate.pop() # 다음 경우의 수 탐색 위해 이전 값 빼주기


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