백트래킹: 선택하고 검사하고 되돌리는 탐색의 구조
백트래킹은 답을 한 단계씩 만들어 보다가 제약을 만족할 수 없는 경우 이전 선택으로 돌아오는 탐색 방식이다. 가능한 모든 완성 후보를 먼저 만든 뒤 검사하는 것보다, 부분 답이 이미 실패한 순간 아래 가지를 버릴 수 있다는 장점이 있다.
현재 선택을 취소해 이전 상태로 돌아간 뒤 다른 가능성을 탐색한다.
N-Queens에서 부분 답을 검사하기
N×N 보드에 퀸 N개를 놓되 같은 행·열·대각선에서 공격하지 못하게 하자. 행마다 하나씩 놓으면 행 충돌은 구조적으로 사라진다. 각 행에서 열을 선택할 때 이전 퀸의 열과 두 대각선이 겹치는지만 검사한다.
def count_queens(board_size):
used_columns, descending, ascending = set(), set(), set()
def place(row):
if row == board_size:
return 1
answers = 0
for column in range(board_size):
if column in used_columns or row-column in descending or row+column in ascending:
continue
used_columns.add(column)
descending.add(row-column)
ascending.add(row+column)
answers += place(row + 1)
used_columns.remove(column)
descending.remove(row-column)
ascending.remove(row+column)
return answers
return place(0)
같은 대각선에서는 row-column 또는 row+column이 일정하다. 두 식을 함께 써야 양쪽 대각선을 모두 막는다. 선택을 추가한 뒤 재귀가 반환하면 정확히 그 선택을 제거하여 다른 열을 독립적으로 시도한다.
가지치기는 안전한 실패 판정이어야 한다
4×4 보드에서 첫 행에 한 퀸을 놓고 둘째 행을 검사하면 같은 열과 대각선 후보들이 즉시 제외된다. 모든 행을 채운 뒤에야 충돌을 검사하는 방식보다 불가능한 부분 배치를 덜 확장한다.
부분 배치의 충돌은 뒤에 퀸을 더 놓아도 사라지지 않으므로 안전한 가지치기다. 반대로 현재 점수가 낮다는 이유만으로 버리려면 이후 큰 점수를 얻을 가능성이 없는지 별도 근거가 필요하다. 불완전한 후보와 불가능한 후보는 다르다.
백트래킹의 최악 시간은 보통 지수적이다. 열 중복을 금지한 N-Queens의 후보 순열 수를 N!로 볼 수 있지만 실제 검사 비용과 방문 노드 수까지 포함해 정확히 표현해야 한다. 가지치기가 있다고 자동으로 다항 시간 알고리즘이 되는 것은 아니다.
재귀 깊이와 현재 선택 정보는 O(N) 수준으로 관리할 수 있다. 모든 해를 저장하면 출력 개수만큼 추가 공간이 필요하다. 위 코드는 해의 수만 누적하므로 완성된 보드를 보관하지 않는다.
제약 만족, 스도쿠, 조합 생성, 퍼즐 풀이에 널리 쓰인다. 후보 순서, 가장 제약이 큰 변수부터 선택하기, 대칭 제거로 실제 탐색량을 줄일 수 있다. 다만 되돌리기에서 공유 상태 하나를 빠뜨리면 다른 분기의 답까지 오염되므로 선택과 해제는 쌍으로 설계해야 한다.