알고리즘💻/Bruteforce&Backtracking
BOJ 9663번: N-Queen
호프
2021. 1. 16. 23:09
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
아이디어:
인덱스 i*j
각 열에 퀸이 하나씩 있어야 한다. for i in (0~N)
1. 같은 행 -> j
2. 오른쪽 위 대각선 -> i+j
3. 오른쪽 아래 대각선 -> i-j+N-1 (인덱스가 음수가 나오면 안되니까)
코드:
파이썬 함수 안에서 변수의 값을 바꾼 후 나와서 출력시킬 때.. 전역변수를 설정해야 한다.
global
import sys
n = int(sys.stdin.readline())
check1 = [False] * n #행 j
check2 = [False] * (n*2-1) #오른쪽 위 대각선 i+j
check3 = [False] * (n*2-1) #오른쪽 아래 대각선 i+j+n-1
ans=0
def solve(i):
global ans #전역변수 설정
if (i==n):
ans+=1
return
for j in range(n):
if (check1[j]==False and check2[i+j]==False and check3[i-j+n-1]==False):
check1[j]=True
check2[i+j]=True
check3[i-j+n-1]=True
solve(i+1)
check1[j]=False
check2[i+j]=False
check3[i-j+n-1]=False
solve(0)
print(ans)