[백준] 9663 N-Queen

[백준] 9663 N-Queen

풀이

백트래킹인 것을 알고 풀어 시간 초과에 대한 생각없이 일단 모든 경우를 모두 탐색해봤다.
퀸을 놓으면 안되는 경우를 제외하면서 퀸을 N개 체스판 위에 올릴 수 있는 경우를 탐색종료 시점으로 잡았다.
먼저 퀸을 각 행마다 하나씩 존재해야 하므로 탐색을 할 때 각 행에서 어떤 열에 놓을 수 있는지 판단했다. 모든 보드판에서 다음 퀸을 어디에 놓을지 생각하려면 너무 복잡해져서 퀸은 행에 하나씩이란 것을 지켜가며 탐색했다. 그러니까 모든 퀸들은 모두 다른 행에 존재하므로 같은 열에 있는지 같은 대각선에 있는지 판단해야 한다.

코드

import sys

N = int(sys.stdin.readline()[:-1])

def NQueen(queen):
    if len(queen) == N:
        return 1
    
    line = [True for _ in range(N)]
    for q in queen:
        # 세로 위치에 있는 격자 제외
        line[q[1]] = False
        # 대각선에 있는 격자 제외 (2가지)
        if 0 <= q[1] - (len(queen) - q[0]) < N:
            line[q[1] - (len(queen) - q[0])] = False
        if 0 <= q[1] + (len(queen) - q[0]) < N:
            line[q[1] + (len(queen) - q[0])] = False

    res = 0
    for i in range(N):
        if line[i]:
            queen.append([len(queen), i])
            res += NQueen(queen)
            queen.pop()
    
    return res

print(NQueen([]))

느낀점

뭔가 맞았는데 시간초과가 나면 제출 언어 설정을 python3 말고 pypy3로 해보자!