[백준] 9663: N-Queens

백트래킹 알고리즘
- DFS
- 가능한 자식 노드들을 전부 탐색하고, 더 이상 진행이 불가능한 경우에는 부모 노드로 다시 돌아옴

아이디어
- n개 퀸을 배치하려면 반드시 각 행마다 하나씩 퀸을 놓아야 함
- 각 행마다 대각선, 세로 여부를 파악하는 solve 함수를 실행
- 현재 행에서 퀸을 배치할 수 있다면 다음 행에 대해 solve 함수를 호출, 그렇지 않다면 이전 행으로 백트래킹
- 하나의 배열에서 상하좌우 모든 경우의 수를 저장하기 보다는 세 개의 배열로 나눠서 정보를 저장

정답코드

# BOJ 9663
import sys
input = sys.stdin.readline

def solve(i):
    global cnt
    
    if i == n:
        cnt += 1
        return
    
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False
                
n, cnt = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

solve(0)
print(cnt)

출처 : https://rebas.kr/761