[알고리즘 일기 - 파이썬] 228. N-Queen

문제 228. (2022-03-30)

 

9663번: N-Queen

Baekjoon 9663. N-Queen

[파이썬(python) - 백트래킹]

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

---

입력

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

 

---

출력

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

 

---

입력 예시

8

 

---

출력 예시

92

 

---

❧ 정답 - pypy 통과

	n = int(input())
	ans = 0
	row = [0] * n
	def backtracking(x):
	for i in range(x):
	if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
	return False
	return True
	def n_queens(x):
	global ans
	if x == n:
	ans += 1
	else:
	for i in range(n):
	row[x] = i
	if backtracking(x):
	n_queens(x+1)
	n_queens(0)
	print(ans)

view raw 0330_N-Queen.py hosted with ❤ by GitHub

🔎 IDEA) 백트래킹 - 백트래킹 조건 설정으로 퀸을 놓을 수 있는지 검사한다.

[Line 6 - 7]
👉 row[x] 에 퀸을 놓았을 때, 해당 칸이 유효한 지를 검사한다.

#8
👉 만약 같은 열 또는 행에 이미 퀸이 있을 경우, 또는 대각선에 퀸이 있을 경우 퀸을 해당 자리에 놓을 수 없으므로 False를 리턴한다.
👉 파라미터 x까지 탐색했을 때, 위의 조건에 모두 걸리지 않는다면 해당 칸에 퀸을 놓을 수 있으므로 True를 리턴한다.

 

[Line 14 - 15]
👉 퀸을 n개 놓았을 경우 ans값을 1 증가시킨다.

 

[Line 17 - 20]
👉 row[x]에 퀸을 놓는 경우가 유효하면 다음 단계를 진행한다. n_queens(x+1) 재귀