백준 9663: N.Queen - 백트래킹(Python/파이썬)

나름 백트래킹을 한다고 했는데 이 코드는 pypy로 돌릴 때만 통과하고 python3은 시간초과가 났다..

다른 사람들은 비트마스킹 쓴 거 같길래 머리 싸매다가 대각선 체크를 O(1)로 하는 법 깨닫다.

1. 우상향 대각선의 경우 같은 줄 내에서 (x, y)의 x+y 값은 항상 같게 유지됨.
2. 우하향 대각선의 경우 같은 줄 내에서 (x, y)의 x-y 값은 항상 같게 유지됨.
   a. 이 때 우하향 대각선 음수가 나올 수 있으므로 가능한 최솟값((0, N-1)의 경우))인 N-1을 일괄적으로 결과값에 더해 0 ~ (2N - 2)의 값을 갖도록 보정.

열/우상향 대각선/우하향 대각선을 각 값을 인덱스로 갖는 1차원 배열을 만들어 체크하는 방식으로 O(1)로 해결.

import sys
input = sys.stdin.readline

def solve(x):
    global ans
    if x == N:
        ans += 1
        return

    for y in range(N):
        if col[y]:
            continue
        elif dia1[x+y]:
            continue
        elif dia2[x-y + N-1]:
            continue

        col[y], dia1[x+y], dia2[x-y + N-1] = 1, 1, 1
        solve(x+1)
        col[y], dia1[x+y], dia2[x-y + N-1] = 0, 0, 0


N = int(input())
col = [0] * N # 해당 행이 사용되었는지 체크
dia1 = [0] * (2*N) # 해당 우상향 대각선 사용되었는지 체크
dia2 = [0] * (2*N) # 해당 우하향 대각선 사용되었는지 체크
ans = 0

solve(0)
print(ans)