[백준] 9663 N-Queen

---

재귀함수를 처음 배울 때 배우는 대표적인 문제중 하나인 N-Queen이다.

 

재귀를 통해 지정한 위치에 Queen을 놓는데 조건이있다. 이전에 놓았던 Queen과 일직선 혹은 대각선 상에 위치하지 않아야한다. 이를 확인하기 위해서 2가지를 확인 해야한다.

 

1. 일직선상에 위치하는 가?

동일한 행에는 Queen이 놓여있지 않기 때문에 이전에 놓았던 Queen 중 같은 열에 위치하는 지 확인한다.

 

2. 대각선상에 위치하는 가?

대각선상에 위치 한다는 것은 두 위치의 가로의 차와 세로의 차의 비교를 통해 확인 가능 하다. 만일 같을 경우 대각선상에 위치하는 것이다.

 

1, 2번 조건을 확인하기 위해서는 보통 열의 번호를 담고있는 배열 하나를 사용하여 반복문을 통해 확인하지만 직선, 대각선1(\), 대각선2(/) 세 가지 배열을 사용하여 확인하는 방법도 존재한다(참고: rebas.kr/761).

 

---

from sys import stdin
readline = stdin.readline

N = int(readline().strip())
a, b, c = [False] * N, [False] * (2 * N-1), [False] * (2 * N-1)
ans = 0

def dfs(level):
    global ans

    if level == N:
        ans += 1
        return
    
    for i in range(N):
        if not(a[i] or b[level+i] or c[level-i+N-1]):
            a[i] = b[level+i] = c[level-i+N-1] = True
            dfs(level+1)
            a[i] = b[level+i] = c[level-i+N-1] = False

dfs(0)
print(ans)