728x90
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1 복사
8
예제 출력 1 복사
92
#코드 : 대각선 부분을 다시한번 알아둘 것.
|
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
36
37
38
39
40
41
42
43
44
45
46
|
import sys
'''
- 대각선 체크
-> 1)왼쪽에서 위협하는 퀸에 대해서
-> 열에서의 차이는 행에서의 차이와 같다
-> col[i] - col[k] == i - k
-> 2)오른쪽에서 위협하는 퀸에 대해서
-> 열에서의 차이는 행에서의 차이의 마이너스 값과 같다.
-> col[i] - col[k] == k - i
-> col[i]와 col[k]의 절댓값으로 대각선 위협을 판단
'''
# i : 깊이(행)
# col : 배열
def n_queens(i, col):
global tot_cnt
n = len(col) - 1
if promising(i, col):
if i == n:
#print(col[1 : n+1]) # 답
tot_cnt += 1
else:
for j in range(1, n+1):
col[i+1] = j
n_queens(i+1, col)
def promising(i, col):
k = 1
flag = True
while k < i and flag:
# 같은 열 or 같은 대각선 체크
if col[i] == col[k] or abs(col[i] - col[k]) == i-k:
flag = False
k+=1
return flag
if __name__ == "__main__":
input = sys.stdin.readline
tot_cnt = 0
n = int(input())
col = [0]*(n+1) # 맨 앞의 0은 시작점.
n_queens(0, col)
print(tot_cnt)
|
cs |
https://www.youtube.com/watch?v=z4wKvYdd6wM
반응형