[백준] 9663번 : N-Queen (Python)

코드의 구현 자체는 간단하다.
DFS를 돌면서, 조건에 맞도록 구현하면 된다.
발목을 잡았던 부분은 바로 시간초과였다. 15 * 15의 경우 상당한 연산 시간이 필요하기 때문으로 보인다. 
이미 이전의 퀸들이 있는 곳은 제외하고 넘어가도록 해야 최대한 시간을 아껴야 통과할 수 있다.
결국 PyPy3에서는 성공했지만, Python3에서는 여전히 시간초과가 발생했다.
Python3에서도 성공하려면 뭔가 다른 방법이 필요할 것으로 보이지만, 시간이 아까우니 패스. 

import sys

N = int(sys.stdin.readline())
row = [0] * N
cnt = 0
visit = [False] * N

# Queen이 서로 공격할 수 없는 지 확인
def check(q):
  for i in range(q):
    if abs(row[q] - row[i]) == q - i: # 대각선에 Queen이 있는지 확인
      return False
  return True

# DFS로 방법으로 탐색
def dfs(q):
  global cnt
  if q == N:
    cnt += 1
    return
    
  for i in range(N): 
    if visit[i]: # 같은 열에 Queen이 있는가
      continue
    
    row[q] = i
    if check(q):
      visit[i] = True
      dfs(q + 1)
      visit[i] = False

dfs(0)
print(cnt)