[백준] 9663 - N Queen (Python)

문제

---

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

 

출력

---

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

예제 입력

---

8

예제 출력

---

92

해결방법

---

N-Queen 문제는 Backtracking 전략을 통해 해결할 수 있는 가장 대표적인 문제중 하나이다. 

Queen을 NxN 체스판에 N개 두기 위해서는 각 행에 오직 하나의 퀸만이 올 수 있다. 

따라서 배열을 하나 만들어서 각 행에 퀸의 위치를 기록할 수 있도록 한다. 

각 행들에 대해 퀸 위치를 모두 탐색하되, 조건에 맞지 않는 경우가 발생한다면 그 이후는 고려하지 않고 가지치기를 해내 경우의 수를 줄인다. 그리고 이전 단계로 되돌아가 탐색을 계속 수행한다. 

정답이 될 가능성이 있는 경로만을 탐색하기 때문에 효율적으로 동작할 수 있다. 

n번째 행에 최종적으로 퀸을 배치하고 공격받는 상태가 아니라면 정답 카운트를 증가시킨다. 

import sys

# 체스판의 크기를 입력받음
n = int(input())

# 현재 배치한 퀸이 이전에 배치한 퀸들과 충돌하는지 확인
def attack(x):
	for i in range(x):
    	# 같은 열에 있거나, 대각선 상에 있으면 충돌임
    	if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
        	return True
    return False

# start는 현재 놓고 있는 행
def dfs(start):
	global cnt
    모든 행에 퀸을 배치했다면 유효한 배치이므로 cnt 증가
    if start == n:
    	cnt += 1
    else:
    	for i in range(n):
        	row[start] = i
            # 충돌이 없다면 다음 행을 진행
            if not attack(start):
            	dfs(start + 1)

# 각 행에 퀸을 저장할 리스트 초기화
row = [0] * n
# 가능한 가짓수를 세는 변수 초기화
cnt = 0
dfs(0)

print(cnt)