호프 2021. 1. 16. 23:09

www.acmicpc.net/problem/9663

 

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)