9663. N-queen

Backtracking으로 풀 수 있다.

 

문제에는 없지만 체스 퀸 이동에 대해서 알고 있어야 한다.

퀸은 상하좌우, 대각선 어느 방향으로든 이동할 수 있기에 공격할 수 없게 놓으기 위해서는 새로 놓고자 하는 퀸이 이미 놓여진 퀸들과 같은 열이나, 행에 있어서도 안되고 대각선 경로에 존재해서도 안된다.

 

여기서 이미 놓여진 퀸들과 "같은 열이나, 행에 있어서는 안 된다"는 것이 핵심이다.

 

그럼 각 행에는 퀸이 한개밖에 올 수 없다는 소리이므로 각 행에 퀸을 하나씩 놓아가면서 탐색할 수 있다.

예를 들어 0번 행의 0번째 열에 1번 퀸을 놓았다면, 1번 행에서는 1번째 열과 대각선 경로에 퀸을 놓지 못한다. 2번째 열에 퀸을 놓았다고 가정하면 대각선 경로와 겹치게 되므로 3번 열에 2번 퀸을 놓을 수 있을 것이다.

2번 행에서는 모두 열 혹은 대각선 경로와 겹치기 때문에 퀸을 놓을 수 없다. 그럼 1번 행으로 돌아가 4번 열에 퀸을 놓아보는 것이다.

 

각 열과 대각선 경로에 대해 퀸을 놓을 수 있는지 체크해주어야 한다.

왼쪽으로 내려가는 대각선 경로 인덱스와 오른쪽으로 내려가는 대각선 경로 인덱스를 정한다. 열을 i로 하고 행을 j라 하면, 좌하향 경로 인덱스는 i+j를 인덱스로, 우하향 경로 인덱스는 i-j+n을 인덱스로 해줄 수 있다. 

우하향 경로는 i-j 값으로 구분되는데 i-j가 음수일 수 있으니 n을 더해준다.

 

위와 같은 과정을 통해 만들어진 코드는 다음과 같다.

 

import sys
input = sys.stdin.readline

n = int(input())
ans = 0
check_col = [False for _ in range(15)]
check_right = [False for _ in range(30)]
check_left = [False for _ in range(30)]

def count_queens(row) :
    global ans
    if row == n :
        ans += 1
        return
    for i in range(n) :
        if check_col[i] or check_right[row-i+n] or check_left[row+i] :
            continue
        check_col[i] = True
        check_right[row-i+n] = True
        check_left[row+i] = True
        count_queens(row+1)
        check_col[i] = False
        check_right[row-i+n] = False
        check_left[row+i] = False

count_queens(0)
print(ans)

True로 체크해주었던 것들은 다시 False로 바꿔줘야 퀸을 다른 곳에 두어도 정상적으로 진행할 수 있다.