728x90
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
와 이거 빡샜다.. 이거 혼자 못 풀고 다른 블로그 참고했음
근데 거기 코드 하나 빠진거있음!!!! pop()을 안 넣었음!!
https://geonlee.tistory.com/40
[BOJ] 👸 N-Queens / 파이썬
👸 N-Queens 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N
geonlee.tistory.com
설명은 위에보면 좋구
코드는 백트래킹인데 29번라인에 pop( ) 넣어서
함수호출 후 다시 빼주는 작업 해야함! 근데 저 블로그 주인분이 코드 긁다가 깜빡 하셨나봄....?
|
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
32
33
34
35
36
37
38
39
40
|
import sys
input = sys.stdin.readline
def nqueen(sol, n):
global cnt
if len(sol) == n:
cnt += 1
return
candidate = list(range(n))
for i in range(len(sol)):
# 같은 열에 있는 후보 지우고
if sol[i] in candidate:
candidate.remove(sol[i])
distance = len(sol) - i
# 오른쪽방향 대각선 지우고
if sol[i] + distance in candidate:
candidate.remove(sol[i] + distance)
# 왼쪽 방향 대각선 지우고
if sol[i] - distance in candidate:
candidate.remove(sol[i] - distance)
# 남은 후보들과 함께 새로운 재귀 출발
if candidate:
for i in candidate:
sol.append(i)
nqueen(sol, n)
sol.pop()
else:
return
num = int(input())
cnt = 0
for i in range(num):
nqueen([i], num)
print(cnt)
|
cs |
728x90
'PS > 백준' 카테고리의 다른 글
| [백준 11866번] 요세푸스 문제 0 (파이썬/python) (0) | 2021.06.15 |
|---|---|
| [백준 1541번] 잃어버린 괄호 (파이썬/python) (0) | 2021.06.15 |
| [백준 2798번 ] 블랙잭 (파이썬/python) (0) | 2021.06.15 |
| [백준 1002번] 터렛 (파이썬/python) (0) | 2021.06.15 |
| [백준 15650번] N과 M (2) (0) | 2021.06.15 |
