1️⃣서론
백준 문제 9663번 N-Queen 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣문제 설명
이 문제는 N * N 의 체스판 위에 퀸 N개를 서로 공격할수 없게 놓는 문제입니다.
보통 N-Queen 문제는 대표적인 백트래킹 문제로 유명하기도 합니다.
혹시 백트래킹을 처음들어본다면 제가 개념을 정리해놓은 곳을 가보시면 될 것 같습니다.
3️⃣풀이
퀸을 한줄씩 놓으면서 답을 찾습니다. 백트래킹 방법으로 수행을 하면 됩니다.
퀸과 퀸이 겹치는 경우는 다음과 같습니다.
- 퀸이 같은 가로줄에 있을때
- 퀸이 같은 세로줄에 있을때
- 퀸이 같은 대각선에 있을때
이 경우를 피해서 DFS로 탐색하며 경우의 수를 찾습니다.
그림을 보면 다음과 같이 찾으면 됩니다.
이를 코드로 나타내면 아래와 같습니다.
4️⃣ 소스코드
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
import sys
n = int(sys.stdin.readline())
def dfs(arr):
global ans
length = len(arr)
if length==n:
ans+=1
return
candidate = list(range(n)) # 후보가 될 수 있는 자리를 0부터 n-1까지 만들고 제외하는 방법을 사용
for i in range(length):
if arr[i] in candidate: # 같은 가로줄에 있으면 후보에서 제외
candidate.remove(arr[i])
distance = length - i
if arr[i] + distance in candidate: # 같은 '/' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] + distance)
if arr[i] - distance in candidate: # 같은 '\' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] - distance)
if candidate:
for i in candidate:
arr.append(i)
dfs(arr)
arr.pop()
else:
return
ans = 0
for i in range(n):
dfs([i])
print(ans)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
