[백준] 9663 N-Queen

https://acmicpc.net/problem/9663 

9663번: N-Queen

n = int(input())

matrix = [[0] * n for _ in range(n)]
result = 0
# 1: 퀸, 0: 놓을수 있는 자리, -1: 놓을수 없는 자리
def backtrack(index, arr=[]):
    if index == n:
        global result
        result += 1

    else:
        for i in range(n): # 한줄에서 하나씩만 보면 됨
            if i in arr: continue
            if matrix[index][i]: continue # 0이 아니면 넘어감
            if check_queen(index, i): continue
            matrix[index][i] = 1
            backtrack(index + 1, arr + [i])
            matrix[index][i] = 0

def check_queen(x, y):
    dx = [-1, -1] #대각선 방향만 확인
    dy = [-1, 1]
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        while 0 <= nx < n and 0 <= ny < n:
            if matrix[nx][ny] == 1:
                return 1
            nx += dx[i]
            ny += dy[i]
    return 0

backtrack(0)
print(result)

이또한 pypy에서만 통과가 되었다....

시간초과가 계속 나는걸 보고있자니 내가 알고리즘을 너무 못하는게 아닌가 싶다.

백트래킹 방식을 사용하되 반복문을 더 많이 사용해봐야하나?