백준 9663번 https://www.acmicpc.net/problem/9663
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
퀸의 특징
상하좌우로 움직일 수 있다.
- 각 행, 열, 대각선에는 한 개의 퀸만 놓을 수 있다.
깊이 우선 탐색
모든 경우의 수를 탐색해야하므로 깊이우선탐색을 사용한다
출력 조건
N 개의 퀸을 놓아야 하므로, 각 행과 각 열에는 한 개의 퀸이 놓여있어야 한다.
- 첫 번째 깊이만 검사한다.
- 모든 행에 퀸을 놓을 수 없으면 False를 반환한다.
위의 조건을 통해서 시간초과를 방지할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def check(x, y):
ai = x - min(x, y)
aj = y - min(x, y)
bi = x + min(x, y)
bj = y - min(x, y)
for k in range(n):
# 왼쪽 위에서 오른쪽 아래 방향
if ai + k < n and aj + k < n and board[ai + k][aj + k] and ai + k != x:
return False
# 오른쪽 위에서 왼쪽 아래 방향
if n > bi - k >= 0 and bj + k < n and board[bi - k][bj + k] and bi - k != x:
return False
return True
def dfs(a, s):
global answer
if a == n: # 퀸이 N개인 경우
answer += 1
else:
for j in range(n):
if isUsed[j] is False:
isUsed[j] = True
board[a][j] = True
if check(a, j):
dfs(a + 1, s + 1) # 각 행에는 한개의 퀸만 둘 수 있다
board[a][j] = False
isUsed[j] = False
if __name__ == '__main__':
n = int(input())
board = [[False] * n for _ in range(n)]
isUsed = [False] * n # 열 중복 체크
answer = 0
dfs(0, 1)
print(answer)