[Algorithm] BaekJoon : 9663. N-Queen by Python

[문제 바로가기] https://www.acmicpc.net/problem/9663

9663번: N-Queen

📌문제 설명

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

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

 

입력

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

 

출력

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

---

💡 문제 풀이

백트래킹의 대표적인 문제 'N-Queen'을 풀었다.
이전에 풀어보았던 문제인데... 내 머리는 청문회인가 보다. ('기억이 나지 않는다...')

 

N X N 체스판을 만든다음 퀸이 놓이는 위치마다 1 표시를 하여 재귀를 진행하면 시간초과가 난다...

따라서, '좌표'단위가 아닌 '줄'단위로 가능한 경우를 찾으면 시간이 매우 단축된다.

N=4 인 경우 탐색해야 하는 '라인'은 위와 같다.

※ 가로의 경우 재귀의 깊이를 '행'으로 하기 때문에 필요X

 

해당 라인에 속하는 좌표를 기준으로 규칙을 찾아 방문여부를 표시하면 된다.

 

ex) 행, 열 = (0, 1)인 경우 방문 표시를 해야하는 라인은 위와 같다(노란색).

※ 인덱스는 0부터 시작

 

1. 세로 방문 여부는 '열'좌표(c)를 따른다. 같은 열좌표면 해당 번호의 라인을 방문처리한다.
2. ↗방향 방문 여부는 r+c+1이다. 좌측 상단부터 1번라인이라고 가정하면 특정 좌표가 속한 라인은 r+c+1이므로 해당 번호의 라인을 방문처리 한다.
3. ↖방향 방문 여부는 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 등 이전에 풀었던 문제임에도 잘 기억이 나지 않았다...
수능 공부를 하듯이 반복 숙달이 필요함을 깨달았다. 😂