2023-10-17-동국대SW역량강화캠프-2861. N-QUEEN
문제
체스라는 게임에서 퀸은 가장 강력한 말로, 가로, 세로, 대각선을 모두 이동할 수 있다.
N * N 크기에 체스 판에 서로를 잡을 수 없도록 퀸을 배치할 때, 최대 N개의 퀸을 배치할 수 있다.
그런데, N이 6보다 큰 경우에는 N개의 퀸을 배치하는 방법이 유일하지는 않다.
N이 주어질 때, N개의 퀸을 배치할 수 있는 방법의 개수를 출력해보자.
입력
체스판의 크기 N이 주어진다.(단, N은 5이상 13이하이다)
출력
퀸을 배치하는 경우의 수를 출력합니다.
예제 1 입력
5
예제 1 출력
10
예제 2 입력
6
예제 2 출력
4
Source
- 정석 방법(파이썬 기준 시간초과)
n = int(input())
ans = 0
arr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
def dfs(x):
global ans
if(x == n + 1):
ans += 1
return
for i in range(1, n + 1):
pos = True
for j in range(1, x):
if(i == arr[j] or j + arr[j] == x + i or
j - arr[j] == x - i):
pos = False
if(pos):
arr[x] = i
dfs(x + 1)
arr[x] = 0
dfs(1)
print(ans)
- 반복문으로 공격가능한 퀸이 있는지 확인하는 방법
n = int(input())
board = [[0 for _ in range(n)] for _ in range(n)]
check = [[0 for _ in range(n)] for _ in range(n)]
count = 0
def dfs(k):
global count
if(k == n):
count += 1
return
for i in range(n):
if(check[k][i] > 0):
continue
# j: 아래로의 변화량
for j in range(n):
if(k + j >= n):
break
check[k + j][i] += 1 # 같은 열 체크
# 왼쪽 위 체크
if(i - j >= 0):
check[k + j][i - j] += 1
# 오른쪽 위 체크
if(i + j < n):
check[k + j][i + j] += 1
dfs(k + 1)
for j in range(n):
if(k + j >= n):
break
check[k + j][i] -= 1
if(i - j >= 0):
check[k + j][i - j] -= 1
if(i + j < n):
check[k + j][i + j] -= 1
dfs(0)
print(count)