[Python] 백준 - 9663 N-Queen

백준 - 9663 N-Queen

문제

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

필요한 도구

 

1. 퀸의 이동방법을 반영할 수 있는 방문리스트 (총 3개)
2. dfs 백트래킹 함수
 

문제해결방법

 

1. dfs함수에서 다음 재귀함수로 넘어가면서 + 되는 변수는 행이다. 행 어딘가에 한번 놓으면 같은 행에는 놓을 수가 없다.
2. 열 또한 같은 열은 직선루트라 놓을 수가 없다.
3. 왼쪽 대각선, 오른쪽 대각선루트도 놓을 수 없다. (대각선은 좌표를 잘보면 규칙성을 찾을 수 있다.)

 
1. 시간초과가 나온다.
2. 체스판의 좌우 대칭성을 이용하여 시간을 줄일 수 있다.
 
1) 짝수일 경우, 좌우대칭으로 반만 계산하면 된다.
2) 홀수일 경우, 위 계산과 더하여 정중앙을 놓았을 때의 cnt를 반영해준다.
 

- 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
v_Q = [0 for _ in range(n)]
v_W = [0 for _ in range(n*2)]
v_E = [0 for _ in range(n*2)]
res, ans = [], []
cnt = 0

def queen(idx):
	global cnt
	if idx == n:
		cnt += 1
		return
	for i in range(n//2 if idx == 0 else n):
		if v_Q[i] == 0 and v_W[i-idx] == 0 and v_E[idx+i] == 0:
			v_Q[i] = 1
			v_W[i-idx] = 1
			v_E[idx+i] = 1
			queen(idx+1)
			v_Q[i] = 0
			v_W[i-idx] = 0
			v_E[idx+i] = 0

if n % 2 != 0:
	queen(0)
	cnt *= 2
	p = n//2
	v_Q[p] = 1
	v_W[p] = 1
	v_E[p] = 1
	queen(1)
	print(cnt)
else:
	queen(0)
	print(cnt*2)