sw사관학교 정글 2기/01 기초,재귀,완전탐색, 정렬

[완전탐색] 백준 N-queen 9663번 with Python3 ★★★

금의야행 2021. 8. 10. 16:40

 

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

 

9663번: N-Queen

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

www.acmicpc.net

 

문제

정답 풀이

n = int(input())
count = 0
pos = [0] * n
flag_a = [False] * n
flag_b = [False] * (n + (n-1))
flag_c = [False] * (n + (n-1))


def set(i: int) -> None:
    global count

    for j in range(n):
        if(not flag_a[j] and not flag_b[i+j] and not flag_c[i-j+(n-1)]):
            pos[j] = j
            if i == (n-1):
                count += 1
            else:
                flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = True
                set(i+1)
                flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)] = False


set(0)

print(count)

출처:

 

해석