https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
n = int(input())
a = [[False] * n for _ in range(n)]
check_col = [False] * n
check_dig = [False] * (2 * n - 1)
check_dig2 = [False] * (2 * n - 1)
def check(row, col):
if check_col[col]: # 수직 검사
return False
if check_dig[row + col]: # 오른 대각선 검사
return False
if check_dig2[row - col + n - 1]: # 왼 대각선 검사
return False
return True # 전부 통과하면 True
def calc(row):
if row == n: # 모든 행을 방문 했을 경우
return 1
ans = 0 # 정답 개수
for col in range(n):
if check(row, col):
check_dig[row + col] = True
check_dig2[row - col + n - 1] = True
check_col[col] = True
a[row][col] = True
ans += calc(row + 1)
# 순회가 끝나고 다음 col을 위해 모두 False로 전환.
check_dig[row + col] = False
check_dig2[row - col + n - 1] = False
check_col[col] = False
a[row][col] = False
return ans
print(calc(0))
대각 방향 check에 대해 미리 모든 일직 대각선상 값이 같은 배열을 만들어서
찾아주는 방식으로 O(1) 가능
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
| [파이썬] 백준 알고리즘 No.16928 뱀과 사다리 게임 (0) | 2022.01.26 |
|---|---|
| [파이썬] 백준 알고리즘 No.3187 양치기 꿍 (0) | 2022.01.24 |
| [파이썬] 백준 알고리즘 No.16198 에너지 모으기 (0) | 2022.01.23 |
| [파이썬] 백준 알고리즘 No.16197 두 동전 (0) | 2022.01.23 |
| [파이썬 (풀이추가예정)] 백준 알고리즘 No.11054 가장 긴 바이토닉 부분 수열 (0) | 2022.01.17 |