문제
n x n 체스판에 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶다.
n은 12이하의 자연수
입출력 예시
| n | result |
|---|---|
| 4 | 2 |
접근
한 줄씩 완전탐색을 해줄 것이다.
한 줄에 퀸이 한개만 와야하는 것은 분명하다.
문제는 대각선을 확인하는 것이다.
이 경우들을 확인하기 위해 각 상태를 저장해둔 배열 3개를 만들었다.
같은 열에 퀸이 있는지, 오른쪽방향과 왼쪽방향으로 대각선에 퀸이 있는지를 담고 있는 배열이다.
대각선의 인덱스 조절에 신경써야하는데 조금 복잡했다.
인덱스 조절만 잘해준다면, 전체 체스판을 탐색할 필요없이 한번에 확인이 가능해진다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
widthCheck = [0 for _ in range(13)]
decreaseCheck = [0 for _ in range(26)]
increaseCheck = [0 for _ in range(26)]
def solution(n):
answer = bp(0, n)
return answer
def bp(cur, n):
cnt = 0
if cur == n:
return 1
for i in range(n):
if widthCheck[i] or decreaseCheck[i+cur] or increaseCheck[n-1+cur-i]:
continue
widthCheck[i] = 1
decreaseCheck[i+cur] = 1
increaseCheck[n-1+cur-i] = 1
cnt += bp(cur+1, n)
widthCheck[i] = 0
decreaseCheck[i+cur] = 0
increaseCheck[n-1+cur-i] = 0
return cnt