2022.04.24 [백준] (python 파이썬) N-Queen
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이
[실전 알고리즘] 0x0C강 - 백트래킹
이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는
blog.encrypted.gg
해당 문제는 위의 블로그에서 공부한 후, 참고하여 해결했습니다.
이 문제를 해결할 때, 퀸이 놓일때마다 체스판에 퀸의 길을 모두 표시하거나 퀸을 놓을때마다 이전 퀸의 이동경로를 모두 확인하기에는 시간이 오래걸린다.
그래서 위의 블로그처럼 3개의 배열을 만들었다.
우선 n이라는 변수가 주어졌을 때, n개의 퀸이 서로 공격할 수 없게 n*n크기의 체스판에 배치할 수 있는 경우의 수를 구해야하기 때문에 각 행에 하나의 퀸만 배치할 수 있다. 그래서 가로는 따로 고려하지 않는다.
그래서 세로에 퀸이 배치되었는가를 확인할 visit1배열을 생성했다.
두번째로 왼쪽 아래에서 오른쪽 위로 올라가는 대각선에 퀸이 배치되었는가를 확인할 visit2배열을 생성했다.
세번째로 왼쪽 위에서 오른쪽 아래로 내려가는 대각선에 퀸이 배치되었는가를 확인할 visit3배열을 생성했다.
그리고 모든 퀸을 서로 공격하지 않게 배치하는 경우의 수를 저장할 cnt변수를 만들었다.
그리고 dfs방식으로 queen함수를 만들었다.
함수에서 cur은 각 행을 뜻하며 만약 cur과 n이 같으면 n개의 퀸이 모두 배치되었기 때문에 cnt를 증가시키고 해당 함수를 빠져나온다.
cur이 n과 같지 않으면 for문을 돌려 cur행에서의 각좌표에 퀸을 배치할 수 있는가를 if문을 통해 판별 후, 배치할 수 있으면 해당 좌표에 퀸을 배치했을 때 갈 수 있는 각 방향의 방문여부배열을 True로 바꿔주었다.
여기서 visit2배열의 인덱스를 cur+i로 한 이유는 예를 들어 (0,3)에 있을 때, 왼쪽 아래에서 오른쪽 위방향의 대각선에 위치한 좌표는 (1,2), (2,1), (3,0)이다. 각 좌표값을 확인하면 x+y값이 같은 것을 확인할 수 있다. 그래서 cur+i를 해주었다.
visit3배열의 인덱스를 cur-i+n-1로 해준 이유는 (0,0)일때 왼쪽 위에서 오른쪽 아래방향의 대각선위에 있는 좌표는 (1,1), (2,2), (3,3)이다. 각 좌표값 x-y의 값이 0으로 같은 것을 확인할 수 있다. 근데 n-1을 따로 해준이유는 만약 좌표가 (0,3)일 경우 음수 값이 나오기 때문에 n일 때 나올 수 있는 가장 작은 음수인 n-1을 0으로 만들어 주기 위해서 이다.
각 배열의 값을 True로 바뀌준 후, 다음 행에 퀸을 배치하기 위해 queen(cur+1)의 함수를 호출하고 이전에 사용한 배열에 대해 False로 초기화 시켜준다.
이유는 해당 경우에 모든 퀸을 배치할 수 없을 때, 다른 경우로 다시 퀸을 새로 배치해야하기 때문이다.
|
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
|
n=int(input())
visit1=[False]*n # 세로
visit2=[False]*(2*n) #왼쪽 아래에서 오른쪽 위
visit3=[False]*(2*n) #왼쪽 위에서 오른쪽 아래
cnt=0
def queen(cur):
global cnt
if cur==n:
cnt+=1
return
for i in range(n):
if not visit1[i] and not visit2[cur+i] and not visit3[cur-i+n-1]:
visit1[i]=True
visit2[cur+i]=True
visit3[cur-i+n-1]=True
queen(cur+1)
visit1[i]=False
visit2[cur+i]=False
visit3[cur-i+n-1]=False
queen(0)
print(cnt)
|
cs |