[문제 바로가기] https://www.acmicpc.net/problem/9663
📌문제 설명
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
💡 문제 풀이
백트래킹의 대표적인 문제 'N-Queen'을 풀었다.
이전에 풀어보았던 문제인데... 내 머리는 청문회인가 보다. ('기억이 나지 않는다...')
N X N 체스판을 만든다음 퀸이 놓이는 위치마다 1 표시를 하여 재귀를 진행하면 시간초과가 난다...
따라서, '좌표'단위가 아닌 '줄'단위로 가능한 경우를 찾으면 시간이 매우 단축된다.
N=4 인 경우 탐색해야 하는 '라인'은 위와 같다.
※ 가로의 경우 재귀의 깊이를 '행'으로 하기 때문에 필요X
해당 라인에 속하는 좌표를 기준으로 규칙을 찾아 방문여부를 표시하면 된다.
ex) 행, 열 = (0, 1)인 경우 방문 표시를 해야하는 라인은 위와 같다(노란색).
※ 인덱스는 0부터 시작
- 세로 방문 여부는 '열'좌표(c)를 따른다. 같은 열좌표면 해당 번호의 라인을 방문처리한다.
- ↗방향 방문 여부는 r+c+1이다. 좌측 상단부터 1번라인이라고 가정하면 특정 좌표가 속한 라인은 r+c+1이므로 해당 번호의 라인을 방문처리 한다.
- ↖방향 방문 여부는 r-c+N이다. 우측 상단부터 1번라인이라고 가정하면 특정 좌표가 속한 라인은 r-c+N이므로 해당 번호의 라인을 방문처리 한다.
step 1)
변수 선언
- v(vertical) : 세로(가로) 방문여부를 파악하는 배열
- r_d(right_diagonal) : ↗방향 방문여부를 파악하는 배열
- l_d(left_diagonal) : ↖방향 방문여부를 파악하는 배열
step 2)
재귀함수를 통해 N-Queen 가능여부를 파악한다. → nqueen 함수
반복문으로 모든 열에 대해서 탐색한다.
이 때, 위에서 구한 규칙을 통해 (r, c)좌표가 속한 라인이 모두 '0'이라면 (아직 놓지 않았거나 서로 공격할 수 없는 경우) '1'로 값을 바꾸어주고 다음 재귀를 진행한다.
이후 완전탐색을 위해 '1'로 표시한 라인을 다시 '0'으로 바꾸어 준다.
재귀의 깊이는 행(r)이므로 N값과 같아지는 경우(=N-Queen 가능) answer+1 해주고 재귀를 종료한다.
- answer : 가능한 N-Queen의 수
코드는 다음과 같다.
import sys
def nqueen(r):
global answer, N
if r == N:
answer += 1
return
for c in range(N):
if not (v[c] or r_d[r+c] or l_d[r-c+N-1]):
v[c] = r_d[r+c] = l_d[r-c+N-1] = 1
nqueen(r+1)
v[c] = r_d[r+c] = l_d[r-c+N-1] = 0
N = int(input())
v, r_d, l_d = [0] * N, [0] * (2*N-1), [0] * (2*N-1)
answer = 0
nqueen(0)
print(answer)LIS, N-Queen 등 이전에 풀었던 문제임에도 잘 기억이 나지 않았다...
수능 공부를 하듯이 반복 숙달이 필요함을 깨달았다. 😂
