[伯俊]9663号N-Queen
https://www.acmicpc.net/problem/9663
質問する
N-Queen問題の大きさはN× これは,N個のチェス盤上のN個の皇后が互いに攻撃し合うことができない問題である.Nが与えられた場合,解放後の方法の数を計算するプログラムを作成してください.
入力
1行目はNです.(1 ≤ N < 15)
しゅつりょく
1行目でN個の皇后が互いに攻撃できない場合は、数字を出力します.
入力例1
8
サンプル出力1
92
に答える
N−Queen問題は遡及アルゴリズムを用いて解く典型的な問題である.backtrackingは、完全ナビゲーション(主にDFS)+条件文(枝切り)と見なすことができます.詳細については、次です。を参照してください.
注記:https://velog.io/@rapsby/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-N-Queen-python
for文と使用するelse文:
https://studymake.tistory.com/208
ソースコード
import sys
input = sys.stdin.readline #입력빠르게받기
#sys.setrecursionlimit(10 ** 6) ##재귀를 사용하므로(★이 문제에서 재귀깊이 늘리면 메모리초과!!)
def dfs(queen, row, N):
count = 0 #이때의 경우의 수 저장할 변수
if N == row: #체스판 넘어감
return 1
for col in range(N): #0부터 N-1번째 열까지
#if visited[col]:
# continue
queen[row]=col #row번째 행의 col번째 열에 퀸 위치시키기
for i in range(row): #0부터 row-1번재 행까지
if queen[i] == queen[row]: #같은열에 존재할 경우
break
if abs(queen[i]-queen[row]) == row -i: #대각선안에 존재할 경우
break
else: #★for문과 짝을 이룬 else문(for문에서 break하면 얘도 수행X)
#visited[col] = True
count += dfs(queen, row+1, N) #row 한칸 이동해서 그때의 경우의수 더하기
#visited[col] = False
return count
N=int(input())
queen = [0]*N #queen[row] = col, row번째 행에는 col열에 queen 위치
#visited=[False]*N
print(dfs(queen, 0, N)) #0번째 행부터 경우 살피기また、アクセス処理により、上記のコードをさらに最適化できます.
Reference
この問題について([伯俊]9663号N-Queen), 我々は、より多くの情報をここで見つけました https://velog.io/@supremo7/백준-9663번-N-Queenテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol