[ BOJ / 파이썬 ] 9663. N-QUEEN

백트래킹을 효율적으로 풀어내는 것과 배열의 대각선 형태의 접근에 대해서 정리할 수 있는 좋은 문제였다.

 

- 배열 사용해서 방문값을 저장해두기 -

 

 

- 대각선 -

왼쪽에서 오른쪽으로 내려오는 대각선 칸들은 같은 줄마다 x+y 값이 같다.

오른쪽에서 왼쪽으로 내려오는 대각선 칸들은 같은 줄마다 x-y+n-1 값이 같다.

 

대각선 개수는 2*n - 1개. 

 

정답코드. 통과.

import sys
input = sys.stdin.readline

def queen(k):
  global result
  if k == n:
    result += 1
    return
    
  for i in range(n):
      if not col[i] and not diagLtoR[i+k] and not diagRtoL[k-i+n-1]:
        col[i] = 1
        diagLtoR[i+k] = 1
        diagRtoL[k-i+n-1] = 1
        queen(k+1)
        col[i] = 0
        diagLtoR[i+k] = 0
        diagRtoL[k-i+n-1] = 0

n = int(input())
result = 0
onBoard = [[0]*(n+1) for _ in range(n+1)]
col = [0]*(n+1)
diagLtoR = [0]*(2*n)
diagRtoL = [0]*(2*n)
queen(0)
print(result)