흰 스타렉스에서 내가 내리지

[BOJ] 9663번 N-Queen 본문

Problem Solving

[BOJ] 9663번 N-Queen

주씨. 2022. 1. 2. 22:43
728x90

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

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n - 1), [False]*(2*n - 1)

def solve(j):
    global ans
    if j == n:
        ans += 1
        return
    
    for i in range(n):
        if not (a[i] or b[i+j] or c[j-i+n-1]):
            a[i] = b[i+j] = c[j-i+n-1] = True
            solve(j+1)
            a[i] = b[i+j] = c[j-i+n-1] = False
            
            
solve(0)
print(ans)

a : 가로줄 , b : 우상좌하 대각선줄, c : 좌상우하 대각선줄 

 

저작자표시

'Problem Solving' 카테고리의 다른 글

[BOJ] 2178번 미로 탐색  (0) 2022.01.02
[BOJ] 10825번 국영수  (0) 2022.01.02
[BOJ] 2110번 공유기 설치 ★  (0) 2022.01.02
[BOJ] 1715번 카드 정렬하기  (0) 2022.01.02
[BOJ] 1005번 ACM Craft  (0) 2022.01.02
'Problem Solving' Related Articles more