[백준]9663 - N-Queen

고려사항

1. 백트래킹 (Backtracking)

• 퀸을 놓을 수 있는 경우 그 행에서 다음 열 탐색하거나 다음 행으로 넘어감
• 퀸을 놓을 수 없는 경우(다른 퀸이 이미 같은 열이나 대각선에 있음) continue로 넘어감, 그 상태에서 다른 열 시도
• 퀸 놓고 재귀호출, 만약 그 경로에서 더 가능하지 않다면 퀸 다시 제거하고 이전 상태로 돌아가 다른 자리에 퀸을 놓으며 새로운 경로 탐색 반복

2. 브루트포스 (Brute Force)

• 모든 행과 열에 대해 퀸 배치 시도

3. 대각선

• n*n 배열에서 한 방향 대각선의 개수는 2*n-1개 (‘/’, ‘\’)
• d1[row-col+n-1]?
  • 같은 ‘/’모양 대각선에 속하는 좌표들은 row-col 값이 같은데, 이 값이 음수가 될 수 있음. (cf. 같은 ‘\‘모양 대각선 좌표들은 row+col값이 같고, 음수 위험 없음)
  • n-1을 더해주어 row-col의 최소값을 0으로 만듦. 직관적으로 대각선을 번호로 표현 가능.

코드

#G4_9663_N-Queen

def dfs(n,row,visited,d1,d2,cnt):
  if row==n:
    return cnt+1
  
  for col in range(n):
    if visited[col] or d1[row-col+n-1] or d2[row+col]:
      continue
    
    visited[col]=True
    d1[row-col+n-1]=True
    d2[row+col]=True

    cnt=dfs(n,row+1,visited,d1,d2,cnt)

    visited[col]=False
    d1[row-col+n-1]=False
    d2[row+col]=False

  return cnt

n=int(input())
visited=[False]*n
d1=[False]*(2*n-1)
d2=[False]*(2*n-1)
cnt=0
print(dfs(n,0,visited,d1,d2,cnt))