9663번: N-Queen

9663번: N-Queen

def dfs(n):
    global ans
    if n == N: #plus case 
        ans+=1
        return
        
    for i in range(N):
        if check_column[i]== check_right_diagonal[n+i] == check_left_diagonal[n-i] == 0:
            check_column[i] = check_right_diagonal[n+i] = check_left_diagonal[n-i] = 1 
            dfs(n+1)
            check_column[i] = check_right_diagonal[n+i] = check_left_diagonal[n-i] = 0 

N = int(input())
ans = 0
check_column = [0] * N
check_right_diagonal = [0] * (2*N)
check_left_diagonal = [0] * (2*N)
dfs(0)
print(ans)

백트래킹을 사용한 N-Queen 문제이다.
대각선과 세로열에 대해서 체크하면서 풀이한 점이 인상깊었다.
대각선은 왼쪽 대각선은 n-i, 오른쪽 대각선은 n+i 의 값이 같다는 성질을 이용했다.
check_column 은 보라색, check_right_diagonal 은 빨간색, check_left_diagonal 은 파란색을 보면 될 것 같다.