[SWEA / PYTHON] 2806. N-Queen

import sys

sys.stdin = open("input/2806_input.txt", "r")

T = int(input())


def check(y, x, possible):
    if True in possible[y]:
        return False

    for i in range(y + 1):
        if possible[y - i][x]:
            return False

    for i in range(1, y + 1):
        if 0 <= y - i and 0 <= x - i:
            if possible[y - i][x - i]:
                return False
        if 0 <= y - i and x + i < N:
            if possible[y - i][x + i]:
                return False

    return True


def dfs(depth, cnt, possible):
    global N, ans
    if depth == N and cnt == N:
        ans += 1
        return

    for i in range(N):
        if check(depth, i, possible):
            possible[depth][i] = True
            dfs(depth + 1, cnt + 1, possible)
            possible[depth][i] = False


for case in range(1, T + 1):
    N = int(input())

    arr = list([0] * N for _ in range(N))
    possible = list([False] * N for _ in range(N))
    ans = 0
    for i in range(N):
        possible[0][i] = True
        dfs(1, 1, possible)
        possible[0][i] = False

    print(f"#{case} {ans}")

풀이.

N * N 크기의 체스판 안에 N 개의 퀸이 서로 공격하지 못하는 위치에 존재해야한다.
퀸은 좌, 우, 대각선으로 움직일 수 있으므로, 한 행과 한 열에 하나의 퀸만 존재해야 한다.
즉, 하나의 열에 반드시 퀸이 존재하므로, (0, 0) 부터 (0, N) 까지의 경우의 수를 전부 조사한다.