9663 N_Queen (python)

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

 

 

 

문제 접근

거의 시간 빠듯하게 제출했다.

DFS로 깡구현하듯 재귀로 깡구현해버렸다

10초라 넉넉해서 이방식으로 했는데 자칫하면 시간초과할뻔했다...

 

x축이 같거나 대각선에 위치하는지 체크하고 모든 포지션에 둬보고 가능하다면 stack에 넣는 방법으로 구현했다.

 

 

 

코드

import sys
input = sys.stdin.readline

"""
앞에 stack에 저장된 값과 현재 위치의 차이의 절대값 x==y라면 ㄴㄴ
"""

def DFS(y):
    if len(stack) == N:
        global ans
        ans+=1
        return
    for x in range(N):
        for sx, sy in stack:
            if sx == x or (abs(sx - x) == abs(sy - y)):
                break
        else:
          stack.append((x,y))
          DFS(y+1)
          stack.remove((x,y))


N = int(input())
ans = 0
stack = []
DFS(0)

print(ans)