[백준 / 파이썬] 9663번: N-Queen

9663번: N-Queen

정답 코드

import sys
input = sys.stdin.readline


def dfs(row, post):
    global answer

    # 종료 조건
    if row == n:
        answer += 1
        return

    # 열 탐색
    for col in range(n):

        # 행, 열 확인
        if not d1[row + col] and not d2[row + n - 1 - col] and not visited[col]:

            visited[col] = True
            d1[row + col] = True
            d2[row + n - 1 - col] = True

            dfs(row + 1, col)

            # 가지치기 / 종료조건 이후
            visited[col] = False
            d1[row + col] = False
            d2[row + n - 1 - col] = False


n = int(input())
visited = [False] * n
d1 = [False] * (n + n + 1)
d2 = [False] * (n + n + 1)
answer = 0

dfs(0, 999999999)

print(answer)

문제 풀이

1. `dfs` 함수에서 `row`가 N과 같아지면 (0부터 시작하므로 N개의 퀸을 모두 배치했을 때), 가능한 경우의 수인 `answer`를 1 증가시킵니다. 이는 하나의 유효한 퀸 배치가 발견되었음을 의미합니다.
2. `for col in range(n)` 반복문을 통해 각 열에 대해 퀸을 배치하려고 시도합니다.
3. `if not d1[row + col] and not d2[row + n - 1 - col] and not visited[col]:` 조건을 통해 해당 열, 대각선 방향에 퀸이 배치되어 있지 않은 경우에만 퀸을 배치합니다.
4. 퀸을 배치한 후에는 `visited`, `d1`, `d2` 리스트를 업데이트하고, 다음 행으로 넘어가는 재귀 호출을 합니다.
5. 재귀 호출이 끝난 후에는 다시 원래 상태로 돌려놓습니다(`visited[col] = False`, `d1[row + col] = False`, `d2[row + n - 1 - col] = False`) 이는 backtracking을 통해 다른 가능한 퀸 배치를 찾기 위한 과정입니다.