[Python] BOJ 9663. N-Queen

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

9663번: N-Queen

NxN 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력하는 문제로 N=4일때를 예시로 들면 다음과 같이 설명할 수 있다

 

4x4 체스판에 퀸 4개가 아래와 같이 있다

 

상태 공간 트리(State-Space Tree)로 1~4번 퀸의 위치를 표현할 수 있다

 

아래는 4개의 퀸들이 서로 공격할 수 없게 놓은 경우의 수 중 하나로, 상태 공간 트리로 표현했을 때는 다음과 같은 경로를 거치게 된다

- 퀸은 현재 위치에서 상하좌우의 직선방향, 대각선 방향으로 움직일 수 있음

코드는 다음과 같다

def is_Possible(x): 
    global board
    for i in range(x): 
    	# 직선방향 검사 or 대각선 방향 검사
        if board[x] == board[i] or abs(board[i]-board[x]) == x-i:
            return False
    return True

def dfs(x):
    global ans, N, board
    if x == N:
        ans += 1
        return
    for i in range(N):
        board[x] = i
        if is_Possible(x):
            dfs(x+1)

N = int(input())
ans = 0
board = [0] * (N)
dfs(0)
print(ans)