# 백준 9663번 N-Queen

## Solution

• PyPy3으로 제출해야 시간 초과가 안 뜬다.
import sys

column = [0] * n

def check(r1, c1, r2, c2):
if c1 == c2:
return False
if r1 - c1 == r2 - c2:
return False
if r1 + c1 == r2 + c2:
return False
return True

def solve(row):
# 퀸 n개를 다 놓음
if row == n:
else:
for col in range(n):
possible = True
for prev_row in range(row):
if not check(row, col, prev_row, column[prev_row]):
possible = False
break
if possible:
# 각 인덱스가 row이고 row 별로 몇 번째 column에 여왕을 놓았는지 저장
column[row] = col
solve(row + 1)
column[row] = 0

solve(0)
print(answer)
• 모범 풀이
import sys
col = [0 for _ in range(n)]
ans = 0

def attackable(r1, c1, r2, c2):
if c1 == c2:
return True
if r1 - c1 == r2 - c2:
return True
if r1 + c1 == r2 + c2:
return True
return False

def rec_func(row):
if row == n:
global ans
ans += 1
else:
for cand in range(n):
possible = True
for i in range(row):
if attackable(row, cand, i, col[i]):
possible = False
break

if possible:
col[row] = cand
rec_func(row + 1)
col[row] = 0

rec_func(0)
print(ans)