[Python/Gold4/9663] N-Queen

|    문제

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

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

|    입력

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

|    출력

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

---

정답 코드

import sys
input =sys.stdin.readline

class Solution:
    def nqueen(self):
        N = int(input())
        
        col = [False] * N
        # y = x
        diag1 = [False] * (2*N-1) # row + col
        # y = -x
        diag2 = [False] * (2*N-1) # row - col
        count = 0
        def backtracking(currentRow):
            nonlocal count
            if currentRow == N:
                count += 1
                return
            
            for j in range(N):
                if not col[j] and not diag1[currentRow+j] and not diag2[currentRow-j]:
                    col[j] = True
                    diag1[currentRow+j] = True
                    diag2[currentRow-j]=True

                    backtracking(currentRow+1)

                    col[j] = False
                    diag1[currentRow+j] = False
                    diag2[currentRow-j]=False
        
        backtracking(0)
        print(count)
if __name__ == "__main__":
    s = Solution()
    s.nqueen()

 

 

|    비고

다시 풀어도 어려운 n-queen 문제이다. n-queen 문제는 구글에 치면 바로 나오는데, 대체 백트래킹으로 어떻게 푸나 싶었다. 다양한 블로그를 참고하여 작성한 첫 코드는 아래와 같다. 열과 대각선을 검사하는 함수를 만들었는데, 시간 초과로 풀리지 않았다.

import sys
input =sys.stdin.readline

class Solution:
    def nqueen(self):
        N = int(input())
        def is_valid(x,y, arr):
            if not arr:
                return True
            for i, j in enumerate(arr):
                if j == y:
                    return False
                if abs(i-x) == abs(j-y):
                    return False
            return True
                
        count = 0
        def backtracking(n, currentRow, arr):
            nonlocal count
            if currentRow == n:
                count += 1
                return
            
            for j in range(n):
                if is_valid(currentRow, j, arr):
                    arr.append(j)
                    backtracking(n, currentRow+1, arr)
                    arr.pop()
        
        backtracking(N, 0, [])
        print(count)
if __name__ == "__main__":
    s = Solution()
    s.nqueen()

 

결국엔 또다시 구글링을 통해 방법을 알아냈는데, 가장 신박했던 건 대각선을 검사하는 방식이었던 거 같다. (i,j) 기준 y= -x 대각선은 row-col(i-j) 값이 같고, y= x 대각선은 row+col(i+j)값이 같았다. 최대 2(N-1)의 값이 되므로, 배열의 크기는 2n -1이 된다.

i-1, j-1	i-1, j	i-1, j+1
i, j-1	i, j	i, j+1
i+1, j-1	i+1, j	i+1, j+1

 

또한, 백트래킹에서 가장 헷갈리는 개념도 정리할 수 있었다.

바로 가지치기(Pruning) 개념이다. 가지치기란 불필요한 탐색 과정을 미리 배제하는 과정으로, 탐색할 때 문제가 해결될 가능성이 없는 경우를 빨리 알아내서 해당 경로를 알지 못하게 하는 것이 이 가지치기의 핵심이다.

정답 코드에선 아래의 부분이 되겠다.

if not col[j] and not diag1[currentRow + j] and not diag2[currentRow - j]:

 

그리고 항상 백트래킹 문제를 풀면, 아래와 같은 공식이 항상 적용되는데 이 코드는 백트래킹의 핵심 동작이다.

col[j] = True
diag1[currentRow + j] = True
diag2[currentRow - j] = True

backtracking(currentRow + 1)

col[j] = False
diag1[currentRow + j] = False
diag2[currentRow - j] = False

 

현재 선택한 경로를 탐색하고, 이후 선택을 취소(복구)하여 다른 경로를 탐색할 수 있도록 만든다.