[BOJ] 9663번 N-Queen (Python)

import sys
input = sys.stdin.readline

N= int(input())
maps = [0]*N # index가 행 index, 값이 열 index
count = 0

def check_to_possible(idx):
  for i in range(idx):
    if maps[i]==maps[idx]: # 같은열 체크
      return False
    if idx - i  == abs(maps[idx]-maps[i]): #대각선 체크
      return False
  return True

def dfs(idx):
  global count
  
  if idx == N: # 마지막까지 도달한 친구일때 count++
    count+=1
    return

  for i in range(N):
    maps[idx] = i # idx행, i열에 둬보기
    if check_to_possible(idx): # 둘 수 있다면
      dfs(idx+1) # 다음 행으로 이동

dfs(0)
print(count)