N-Queen 문제는 n x n 체스판에 n개의 퀸이 서로 공격하지 않는 경우의 수를 구하는 문제이다.
퀸의 공격 방향은 행, 열, 위쪽 대각선(/), 아래 대각선()이다.
- 모든 분기를 확인할 필요 없이 퀸이 있는 행, 열, 위쪽 대각선(/), 아래 대각선()은 제외하고 탐색한다.
- 각 행에 퀸을 하나씩 배치
- 0행부터 시작하여, 각 열 위치에 퀸을 둘 수 있는지 확인
- 퀸을 둘 수 있는 경우, 다음 행으로 넘어가 계속해서 배치
- 같은 열 또는 대각선에 퀸이 있는 경우, 해당 열 패스
- 0행부터 n−1행까지 모두 퀸을 배치한 경우, 배치 성공
- 대각선은 각 행열의 인덱스의 합과 차로 확인
import sys
input = sys.stdin.readline
n = int(input())
cols = [False] * n # 열 정보
flag_a = [False] * (2 * n - 1) # / 대각선 정보
flag_b = [False] * (2 * n - 1) # \ 대각선 정보
def place_row(i):
if i >= n:
return 1
count = 0
for j in range(n):
if (not cols[j] and not flag_a[i + j] and not flag_b[i - j + n - 1]):
cols[j] = flag_a[i + j] = flag_b[i - j + n - 1] = True
count += place_row(i + 1)
cols[j] = flag_a[i + j] = flag_b[i - j + n - 1] = False
return count
print(place_row(0))