Problem Solving
[BOJ] 9663번 N-Queen
주씨.
2022. 1. 2. 22:43
728x90
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n - 1), [False]*(2*n - 1)
def solve(j):
global ans
if j == n:
ans += 1
return
for i in range(n):
if not (a[i] or b[i+j] or c[j-i+n-1]):
a[i] = b[i+j] = c[j-i+n-1] = True
solve(j+1)
a[i] = b[i+j] = c[j-i+n-1] = False
solve(0)
print(ans)a : 가로줄 , b : 우상좌하 대각선줄, c : 좌상우하 대각선줄