[백준 9663. N-Queen]

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

재귀와 백트래킹을 활용하였다.
가로, 세로, 대각선을 검사하는 세가지 배열을 만들고, 같은 줄에 퀸이 있다면 패스
없다면 다음 행으로 진행하며 N행 까지 도달할 경우 카운트하는 방식으로 풀었다.

import sys

input = sys.stdin.readline


def dfs(num):
    global ans
    # N행까지 왔다면 완료
    if num == N:
        ans += 1
        return

    for j in range(N):
        # 열, 대각에 퀸 없다면
        if v1[j] == 0 and v2[j+num] == 0 and v3[j-num] == 0:
            # 체크하고 아래 행으로 재귀호출
            v1[j] = v2[j+num] = v3[j-num] = 1
            dfs(num + 1)
            # 탐색 끝났으면 체크 해제하고 다음 칸으로 이동
            v1[j] = v2[j + num] = v3[j - num] = 0


N = int(input())
ans = 0
# 열, 왼쪽 대각, 오른쪽대각 퀸 있는지 체크 배열
v1, v2, v3 = [[0] * (N * 2) for _ in range(3)]

dfs(0)
print(ans)