[백준] N-Queen | 파이썬 | 백트래킹

https://www.acmicpc.net/problem/9663

문제

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.

퀸을 하나 놓을 때마다 해당 칸을 포함하는 가로, 세로, 대각선에 위치한 칸에는 다른 퀸을 놓을 수 없다.
하나의 row(행)에 대해서 열, 상향대각선, 하향대각선에 퀸을 놓을 수 있는지 검사함.

def solution(n):
    columns = [False] * n # 열(세로) 체크하기 위한 배열
    diag_up = [False] * (2 * n - 1) # 상향 대각선 체크하는 배열
    diag_down = [False] * (2 * n - 1) # 하향 대각선 체크하는 배열

    return backtracking(0, n, columns, diag_up, diag_down)

N x N 정사각형에 대해서 각 방향의 대각선 개수는 (2N-2)개
0번행(첫번째 행)부터 퀸을 놓을 수 있는지 검사하는 함수 호출

def backtracking(row, n, columns, diag_up, diag_down):
    if row == n:  # 모든 퀸을 배치한 경우
        return 1

row : 현재 배치 중인 행
row == n 이면 퀸을 모두 놓은 경우, 하나의 배치 방법을 찾았으므로 1을 리턴

    answers = 0
    for col in range(n):  # 현재 row에서 모든 열(col)에 대해 시도
        if columns[col] or diag_up[row + col] or diag_down[row - col + n - 1]:
            continue  # 퀸을 놓을 수 없는 위치면 스킵

각 행에서 모든 열에 퀸을 놓을 수 있는지 확인
열 & 상향 대각선 & 하향 대각선에 이미 퀸이 있는지 확인
셋 중 하나라도 있으면 스킵

        columns[col] = True
        diag_up[row + col] = True
        diag_down[row - col + n - 1] = True

퀸을 놓을 수 있다면, 그 위치에 퀸을 놓았다고 가정하고 True로 설정

        answers += backtracking(row + 1, n, columns, diag_up, diag_down)

다음 행으로 넘어감, answers 에는 경우의 수 누적

        columns[col] = False
        diag_up[row + col] = False
        diag_down[row - col + n - 1] = False

재귀가 끝나면 다음 경우의 수를 탐색하기 위해 퀸을 회수하고 원래대로 되돌려 놓음(백트래킹)

📒 최종 코드

def backtracking(row, n, columns, diag_up, diag_down):
    # n개의 퀸을 모두 배치한 경우
    if row == n:
        return 1

    answers = 0
    for col in range(n):
        if columns[col] or diag_up[row + col] or diag_down[row - col + n - 1]:
            continue

        columns[col] = True
        diag_up[row + col] = True
        diag_down[row - col + n - 1] = True

        answers += backtracking(row + 1, n, columns, diag_up, diag_down)

        columns[col] = False
        diag_up[row + col] = False
        diag_down[row - col + n - 1] = False

    return answers

def solution(n):
    columns = [False] * n
    diag_up = [False] * (2 * n - 1) 
    diag_down = [False] * (2 * n - 1) 

    return backtracking(0, n, columns, diag_up, diag_down)