💡문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제입력
8예제출력
92📖내가 작성한 code
def DFS(L):
global cnt
if L==n:
cnt+=1
return
else:
for i in range(n):
if L+i in diag1 or L-i in diag2 or i in col:
continue
col.add(i)
diag1.add(L+i)
diag2.add(L-i)
DFS(L+1)
col.remove(i)
diag1.remove(L+i)
diag2.remove(L-i)
n=int(input())
cnt=0
col,diag1,diag2=set(),set(),set()
DFS(0)
print(cnt)
👩
행을 기준으로 해서 행을 증가시키면서 비교를 했다.
대각선의 경우, 행과 열의 합이 같거나 차가 같을 경우에 한 대각선위에 있다.
파이썬으로 계속 시간초과가 나서 PyPy3로 제출했다.
대신 메모리가 많으므로 푸는 무제의 종류에 따라 선택적으로 사용하는 것이 중요한듯
