[백준] 9663번 : N-Queen

 

import sys

Board = int(sys.stdin.readline())
row = [0] * Board
count = 0
gone = [False] * Board


# 퀸이 서로 공격할 수 없는지 체크
def check(q):
    for i in range(q):
        if abs(row[q] - row[i]) == q - i:  # 대각선에 퀸의 존재여부 체크
            return False
    return True


# DFS(깊이우선탐색)으로 방법으로 탐색
def dfs(q):
    global count
    if q == Board:
        count += 1
        return

    for i in range(Board):
        if gone[i]:  # 같은 열에 퀸의 존재여부 확인
            continue

        row[q] = i
        if check(q):
            gone[i] = True
            dfs(q + 1)
            gone[i] = False


dfs(0)
print(count)

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