백트래킹 (back tracking)
즉, 백트레킹은 트리구조를 기반으로 DFS 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리에서 조건을 만족하지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지를 쳐버림 (Pruning)
상태공간트리 (State Space Tree)
문제 해결과정의 중간상태를 각각의 노드로 나타낸 트리
예시문제
N Queen 문제
N X N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
퀸은 다음과 같이 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야함
퀸: 수직, 수평, 대각선 이동(공격) 가능, 따라서 다음 예와 같이 배치
Pruning (가지치기)
Promising
코드
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 --------------------------------------------------- solve_n_queens(4)