9663号nQueen。py

問題の概要

0.すべての状況を考慮した数量

1.バックトレース

状態空間ツリー(N=4)

import sys
input = sys.stdin.readline

n = int(input())

def dfs(row):
    global count
    if row == n:
        count += 1   # 백트래킹을 통해서 마지막까지 도달했기 때문에 count += 1
        return
    for col in range(n):
        queen[row] = col    # 행에 모든 경우의 수를 넣는다. (row, col) 위치에 퀸을 놓으면
        for i in range(row):    # 대각선과 열에 퀸이 있는 확인
            if queen[i] == queen[row] or abs(queen[i]-queen[row]) == row - i:
                break
        else:
            # `else :` 는 break 를 만나지 않고 무사히 `for i in range (row)`을 통과하면 실행된다.
            # 즉 퀸이 현재 위치에 있어도 된다는 의미로 검사를 진행한다.
            dfs(row + 1)

queen = [0] * n
count = 0
dfs(0)
print(count)