백준 9633번 NQueen 파이썬 (python code)

난이도: 골드5
번호:9633번

백트래킹문제로 python3는 시간을 만족시키지 못해 pypy3로 제출하여 통과하였다.

row를 기준으로 한줄씩 내려가면서 모든 column에 숫자를 넣을 수 있는지 체크하면서 풀어내려갔다.

from sys import stdin

def queendfs(row):
global count
if (row==N):
count +=1
return
for j in range(N):
checkpoint = True
for n in range(len(queenlist)):
if queenlist[n][1] == j or abs(queenlist[n][0] - row) - abs(queenlist[n][1] - j) == 0:
checkpoint=False
break
if checkpoint==True:
queenlist.append([row,j])
queendfs(row+1)
queenlist.pop()

if __name__ == '__main__':
N= int(stdin.readline().rstrip())
count=0
queenlist=[]
queendfs(0)
print(count)