[파이썬][알고리즘] 백트래킹

백 트래킹 기법

• 백 트래킹 또는 퇴각 검색이라 칭함
• 제약 조건 만족 문제를 풀기 위한 전략
  • 후보군의 제약 조건을 체크하다가 만족할 수 없다고 판단되면 backtrack (다시는 이 후보군을 체크하지 않음), 그 후 다른 후보군으로 넘어감
  • 계산의 양을 줄일 수 있음
• 모든 경우의 수를 상태 공간 트리로 표현
  • 각 후보군을 DFS로 탐색
  • 제약기 맞지 않으면 해의 후보가 될만한 곳으로 넘어가서 탐색
  • Promising: 조건이 맞는지 검사
  • Pruning: 조건이 맞지 않으면 다른 루트로 가서 탐색, 시간 절약
• DFS로 탐색을 진행하면서 조건에 부합하는지 체크하고 부합하지 않으면 다른 루트로 가서 DFS 탐색을 진행

N Queen 문제

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

Pruning

• 한 행에는 하나의 퀸만 위치함
• 체스판을 좌표로 나타낸 후 맨 위에 있는 행부터 퀸을 배치
• 다음 행에 이전에 배치한 퀸이 이동할 수 없는 위치를 찾아 퀸 배치
• 이전 행에 배치한 퀸으로 인해 다음 행에 퀸을 놓을 수 없는 경우 퀸을 배치하지 않고 이전 퀸의 자리 이동
• 이를 이용하여 트리형태로 만듦

Promising

• 퀸의 이동 경로에서 수직과 대각선을 체크
  • 한 행에 한개의 퀸만 위치하므로 수평 체크는 필요 없음
• 수직 체크: 열이 달라야 함
• 대각선 체크: 행과 열의 차이가 같은지 다른지 확인 (같으면 대각선에 위치한 것)

코드 작성

def nqueen(n):
    result = []
    dfs(n, 0, [], result)
    return result


def dfs(n, current_row, current_candidate, result):
    # 배치 종료
    if current_row == n:
        result.append(current_candidate[:])
        return

    # current_row에서 배치할 수 있는 col 찾기
    for candidate_col in range(n):
        if possible(current_candidate, candidate_col):
            current_candidate.append(candidate_col)
            dfs(n, current_row + 1, current_candidate, result)
            current_candidate.pop()


# 이전에 배치한 퀸과 같은 열에 있거나 대각선에 있으면 False
def possible(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

nqueen(4)

[[1, 3, 0, 2], [2, 0, 3, 1]]

nqueen(5)

[[0, 2, 4, 1, 3],
 [0, 3, 1, 4, 2],
 [1, 3, 0, 2, 4],
 [1, 4, 2, 0, 3],
 [2, 0, 3, 1, 4],
 [2, 4, 1, 3, 0],
 [3, 0, 2, 4, 1],
 [3, 1, 4, 2, 0],
 [4, 1, 3, 0, 2],
 [4, 2, 0, 3, 1]]