[알고리즘10] 백트래킹 (N Queen)

---

백트래킹 

 

백트래킹(Backtracking)이란,

제약조건을 만족하는 해를 찾기 위한 전략으로, 문제를 푸는 일종의 전략, 기법이라고 볼 수 있다 (알고리즘은 아님)

후보군을 점진적으로 체크하다가 제약조건을 만족하지 못한다고 판단되면 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것이라고 표기) 한다. 다음 후보군을 체크해 나가며 결국 최적의 해를 찾는 방법이다.

 

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

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

 

즉, 백트래킹은 트리구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크(Promising), 만약 해당 트리(나무)에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이탐색을 진행하지 않고 가지를 쳐버림(Pruning)

 

 

백트래킹 구현 방법

1. 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현한다.

여기서 상태공간트리란 문제해결과정의 중간상태를 노드로 나타낸 트리.

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

3. 트리를 탐색하면서 제약이 맞지 않으면, 해의 후보가 될 만한 곳으로 바로 넘어가서 탐색한다.

 

 

 

---

N Queen 문제

 

N Queen

대표적인 백트래킹 문제로, N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제.

퀸은 상하좌우, 대각선으로 이동할 수 있으므로, 배치된 퀸 간에 공격할 수 없는 위치로 배치해야 한다.

Promising: 해당루트가 조건(퀸과 수직, 수평, 대각선에 위치하지 않음)에 맞는지 검사하는 기법

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

 

 

 

 

---

파이썬으로 백트래킹 N Queen 구현하기

 

1. Promising: 수직 체크와 대각선 체크 

수직 체크: candidate[queen_row] == current_col

대각선 체크: abs(candidate[queen_row] - current_col) == current_row - queen_row

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

 

2. Pruning(가지치기)

 

1) if문 이용해 탈출조건 구현

2) pop() 이용해 backtracking 한다. ( 최적위치 찾았으면 return됨. DFS를 빠져나왔다는 것은 실패했다는 뜻 )

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() # backtraking

n은 row의 전체 줄 수

current_row 현재 검사하고자 하는 row

current_candidate 지금까지 배치된 퀸의 위치가 저장되어 있음

final_result 퀸의 배치조건을 모두 만족하는 n개의 퀸 위치가 저장되어 있음

 

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


solve_n_queens(4) # [[1, 3, 0, 2], [2, 0, 3, 1]]