215. NQUEENS
1) 어떤 전략(알고리즘)으로 해결?
백트래킹
2) 코딩 설명
- 주석 설명
- PROMISING 추가 설명
3) 문제 설명
<내 풀이>
n = int(input()) # N은 depth (우리가 놓고자 하는 퀸 갯수 & 표의 행,열)
ans = 0 # 경우의 수
col = [0] * n # N 만큼의 ROW 가 존재
______________________________________________________________________
# 가지치기 판별 조건 - 백트래킹 특징
# 내 이전 행들에서 퀸이 놓인 위치를 볼건데,
# 이 위치의 열이 내가 지금 놓인 열이랑 똑같거나 대각선에 놓인거면
# 퀸 조건 X , 가지치기 끊어야 함 (FALSE)
def is_promising(x):
for i in range(x): # 0부터 X-1까지의 행 => 즉 자신 이전의 행
if col[x] == col[i] or abs(col[x] - col[i]) == abs(x - i):
return False
return True
______________________________________________________________________
# 가지치기용 재귀 함수
def n_queens(x): # X 행인 경우
global ans
if x == n:
# 우리가 찾고자 하는 경우 (x가 N이 됐다는 것은 0행부터 N-1행까지 하나씩 다 놓인 것)
ans += 1
return
else:
for i in range(n): # X행의 퀸이 놓일 열 검사 (0부터 N-1까지)
col[x] = i # x번째 행의 열은 i라는 의미
# x행에 있는 퀸이 i번째 열에 놓였을 때 다음 행으로 이동해야 하는데
if is_promising(x): # i번째 열에 놓였을 때
n_queens(x+1)
# for문으로 n번 돌았는데도 (내 행에서 놓일 열의 경우 수 모두 검사)
# 이번 행에서는 놓일 열이 없으면
# 한 행에 하나씩은 놓여야 N개 퀸이 되므로
# 이번 가지는 N퀸 가망이 없는 것, 재귀 종료 => 가지 쳐주는 것
______________________________________________________________________
n_queens(0) # 0행에 퀸을 놓는 것으로 시작
print(ans)
<배운 점>
백트래킹 개념
N퀸 완전 이해
