N-Queen 문제이다.
카테고리상 DFS와 백트래킹 그리고 완전탐색에 분류되며 백트래킹의 대표격이 되는 문제이다.
본인은 재귀, 그래프에 상당히 취약한 스타일로 일단 유튜브, 블로그 등을 탐방하며 백 트래킹에 대한 틀을 잡고 문제를 풀었다.
일단 N-Queen
이라 함은 n x n만큼의 크기를 갖는 체스판에 n개의 퀸을 두되, 서로가 간섭할 수 없는 위치에 퀸을 두는 것을 의미한다.
따라서 현재 위치에 퀸을 두고 다음 위치에 퀸을 둘 수 있는가 없는가를 확인하기 위해 promising(idx)
함수를 사용하여 검증 후 반환값에 따라 다음 순서로 진행하도록 하며 이 과정을 가지치기
단계라고 본다.
만약 갈수 없음에도 불구하고 진행하게 된다면 모든 경우의 수를 확인해야 하기 때문에 효율적인 측면에서 이렇게 가지치기
를 수행하는 것이다.
문제를 해결하기 위해 두개의 함수로 진행이 된다.
1. dfs(idx)
dfs
와 큰 차이가 없다.def dfs(idx):
# 전체 순회를 마쳤는가?
if idx == n:
global result
# 같을 경우 결과값 추가
result += 1
return
for i in range(n):
# 현재 위치를 저장
board[idx] = i
# 다음 위치에 퀸을 둘 수 있는가를 확인하기 위한 promising함수 수행
if promising(idx):
dfs(idx + 1)
promising(idx)
idx
가 조건을 만족할 경우에 대해서 참값을 반환하도록 구성def promising(idx):
for i in range(idx):
if board[idx] == board[i] or abs(board[idx] - board[i]) == abs(idx - i):
return False
return True
import sys
n = int(sys.stdin.readline())
board = [0] * n
result = 0
def promising(idx):
for i in range(idx):
if board[idx] == board[i] or abs(board[idx] - board[i]) == abs(idx - i):
return False
return True
def dfs(idx):
if idx == n:
global result
result += 1
return
for i in range(n):
board[idx] = i
if promising(idx):
dfs(idx + 1)
dfs(0)
print(result)