[BOJ 파이썬] - N-Queen (9663번)

백트래킹의 대표적인 문제 N-Queen입니다.

접근

n개의 퀸을 n*n 크기의 판에 겹치지 않기 위해 둘 때 체크해야할 부분은 가로, 세로, 대각선에 어떤 퀸도 겹치지 않느냐 입니다.

우선 가로는 n번의 반복문을 통해 한줄에 하나의 퀸만 배치하는 것으로 해결합니다.

그 다음 세로는 체크 배열을 만들어 해당 줄이 사용되었는지 확인합니다.

세번째 대각선은 해당 줄에서 위에 해당되는 줄에서 겹치는 것이 없는지 확인합니다.

이 모든 규칙들을 지키면서 맨 아랫줄 까지 도달하면 겹치지 않고 모든 퀸을 배치했다는 것이므로 answer에 1의 경우를 추가해 줍니다.

풀이

import sys
n = int(sys.stdin.readline())
a = [[0] * n for _ in range(n)]

def DFS(level):
  global answer
  if level == n:
    answer += 1
    return
  else:
    for i in range(n):
      if ch[i] == 0:
        step = 1
        for j in range(level-1, -1, -1):
          if 0 <= i - step and a[j][i - step] != 0: break
          if i + step < n and a[j][i + step] != 0: break
          step += 1
        else:
          a[level][i] = 1
          ch[i] = 1
          DFS(level+1)
          a[level][i] = 0
          ch[i] = 0

ch = [0] * n
answer = 0
DFS(0)
print(answer)

여담

해당 코드는 파이썬을 통해서는 시간 초과가 발생하여 pypy3를 사용해야만 통과가 됩니다.