AEKJOON #9663 N-Queen (backtracking, DFS) - python
N-Queen
출처 : 백준 #9663
시간 제한 | 메모리 제한 |
---|---|
10초 | 128MB |
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
입출력 예시
예제 입력 1
8
예제 출력 1
92
풀이
- 관련 개념 : Algorithm-class-Backtracking
생각
- N-Queen 문제는 backtracking 유형의 가장 대표적인 문제이다.
- 같은 열, 같은 행, 대각선에 위치하면 안되게끔 N개의 Queen을 놓아야 한다.
- bounding function(여기서
place 함수
)를 어떻게 짜느냐가 관건이다.- 여기서는 for문을 0부터 k-1까지 돌면서 아래 항목을 체크한다.
- 같은 열에 위치하는지? :
(board[j] == i)
- 대각선에 위치하는지? :
(abs(board[j]-i) == abs(j-k))
- 대각선의 경우에는 기울기가 1 or -1이므로 위와 같은 식으로 계산된다.
- 같은 열에 위치하는지? :
- 여기서는 for문을 0부터 k-1까지 돌면서 아래 항목을 체크한다.
- 본 함수인
backtrack
에서는 for문을 0부터 n-1까지 돌면서 place 함수를 통과했다면, k가 도착점에 도착했는지 아닌지를 판별한 후 도착했다면count
를 1 증가 시키고 아니라면 k에 1을 더한 값을 재귀적으로 돌린다.
python code
# 백준 9663번 N-Queen
from sys import stdin
input = stdin.readline
n = int(input())
board = [-1]*n
count = 0
def backtrack(board, k, n):
global count
for i in range(n):
if place(board, k, i):
board[k] = i
if k == n-1:
count += 1
# print('chess :', end=" ")
# for j in range(n):
# print(board[j], end=" ")
# print()
return
else:
backtrack(board, k+1, n)
def place(board, k, i):
for j in range(k):
if (board[j] == i) or (abs(board[j]-i) == abs(j-k)):
return False
return True
backtrack(board, 0, n)
print(count)
Author And Source
이 문제에 관하여(AEKJOON #9663 N-Queen (backtracking, DFS) - python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nathan29849/BAEKJOON-9663-N-Queen-backtracking-DFS-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)