[백준] 9663번(python 파이썬)

https://www.acmicpc.net/problem/9663

 

NxN크기의 체스판이 주어졌을때 퀸을 서로 공격할 수 없게 N개 놓을 수 있다.

 

N개를 놓을 수 있는 경우의 수를 구하는 문제인다.

 

N개를 놓을 수 있다는 것은 한 행에 한개씩 놓을 수 있으면 된다는 소리이다.

 

퀸은 대각선, 열, 행 이렇게 움직일 수 있다.

 

즉, 어떤 위치에 퀸이 놓여지면 해당 대각선, 행, 열은 더이상 다른 퀸을 놓을 수 없게 된다.

 

해당 행에서 열을 순회하면서 놓을수 없는지 판단하며 상태 트리를 만들게 된다.

 

ex)

퀸이 0,0에 있다면

0,0에 퀸을 놓았다면 1,2에 놓을 수 있다. 

1,2에 퀸을 놓았는데 행이 2인 곳에 퀸을 놓을 수 있는 자리가 없기 때문에 이전 상태로 올라간다.

1,3에 퀸을 놓으면 2,1에 퀸을 놓을 수 있다.

2,1에 퀸을 놓았는데 행이 3인 곳에 퀸을 놓을 수 있는 자리가 없기 떄문에 이전상태로 올라간다.

이전상태로 올라갔는데 열을 모두 순회했기 때문에 또 이전 상태로 돌아간다.

 

이제 0,1에 퀸을 놓을 차례이다...

 

즉 조건을 확인하면서 놓을 수 있는지 확인해야 하는데 이는 해당 열에 이미 퀸이 놓여져 있는지와 해당 대각선에 이미 퀸이 놓여져있는지를 확인하면 된다. 

 

때문에 열에 해당하는 배열 1개와 대각선에 해당하는 배열 2개를 만들어서 체크를 한다.

 

isused1 = [False] * n #열
isused2 = [False] * ((n-1) * 2 + 1) #오른쪽 위 대각선 x+y
isused3 = [False] * ((n-1) * 2 + 1) #오른쪽 아래 대각선 x-y+n-1

 

같은 대각선에 있는 좌표는 x+y(오른쪽 위로 향하는 대각선)가 같거나 x-y(오른쪽 아래로 향하는 대각선)가 같은 속성을 같는다.

 

n = int(input())

count = 0
isused1 = [False] * n #열
isused2 = [False] * ((n-1) * 2 + 1) #오른쪽 위 대각선 x+y
isused3 = [False] * ((n-1) * 2 + 1) #오른쪽 아래 대각선 x-y+n-1

def BackT(depth):
    global count

    if depth == n:
        count += 1
        return

    for i in range(n):
        if isused1[i] or isused2[i + depth] or isused3[i - depth + n - 1]:
            continue

        isused1[i] = True
        isused2[i + depth] = True
        isused3[i - depth + n - 1] = True
        BackT(depth + 1)
        isused1[i] = False
        isused2[i + depth] = False
        isused3[i - depth + n - 1] = False

BackT(0)
print(count)