[알고리즘 종류] 백 트랙킹 (Backtracking)

- 백트랙킹

• 해결책에 대한 후보를 구축해 나아가다 가능성(promising)이 없다고 판단되는 즉시 후보를 포기하고 다른 후보군으로 넘어가며 정답을 찾아가는 알고리즘
• DFS + Pruning(가지치기). 보통 DFS의 재귀로 구현함.
• 안 되는 조건은 없애면서 탐색하기 때문에 시간복잡도가 선형적으로 증가할 법한 문제에서 백트래킹을 적용하면 시간복잡도를 줄일 수 있음.

- 절차

1. *상태 공간 트리의 깊이우선 검색 실시

2. 각 노드가 유망한지 점검

3. 유망하지 않으면 , 그 노드의 부모 노드로 돌아가서 검색 계속

 

*상태 공간 트리: 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리

 

활용 예제

ex) N queen 문제

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

- 한행에는 하나의 퀸 밖에 위치할수 없음.

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

- 만약 앞선 행에 배치한 퀸으로 인해, 다음 행에 해당 퀸들이 이동할 수 있는 위치가 없을 경우에는, 더이상 퀸을 배치하지 않고, 이전 행의 퀸의 배치를 바꿈.

 

def is_available(candidate, current_col):
    current_row = len(candidate)
    for queen_row in range(len(candidate)): # 전의 queen과 열이 같고 대각선이면 가능성 없음!
        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, queens, final_result):
    if current_row == N:
        final_result.append(queens[:])
        return

    for candidate_col in range(N):
        if is_available(queens, candidate_col):  # 가지치기 조건
            queens.append(candidate_col)
            dfs(N, current_row + 1, queens, final_result)
            queens.pop()

N = int(input())
final_result = []
dfs(N, 0, [], final_result)
print(final_result)

https://www.fun-coding.org/Chapter21-backtracking-live.html 참고