(Python) - BOJ(9663번) : N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

• 문제 : 

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

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

 

 

 

 

---

• 풀이 :

N-Queen 문제는 풀 때마다 공부를 더 해야겠다는 생각만 든다. 

 

원래 N-Queen문제는 브루트포스를 이용한 dfs 구현이지만 적절한 조건에서 프루닝을 해준다면 효율적인 백 트래킹으로 풀 수 있다. 브루트포스로 해결하면 안되는 이유는 모든 경우가 O(N^N) 이므로 N이 커지면 그 시간이 말도안되게 오래걸리기 때문이다. 

 

푸는 방법은 다음과 같다.

 

1.  0번 row부터 N-1 row까지 각 행들에 대해 N개의 열을 탐색하며 퀸을 놓을 수 있는지 ( 가로, 세로, 대각선에 이미 놓인 퀸이 없는지) 검사하고 놓을 수 있다면 말을 놓고 row+1을 탐색한다.
2.  row가 N이라면 퀸을 N개 놓았다는 것이므로 정답 카운트를 1 해준다.

 

처음에는 말판을 구현하기 위해 NxN의 2차원 배열을 구현하려 했다. 물론 이 방법도 사용 가능하다. 그러나 더 쉬운 방법이 있었다.

 

(i,j)에 말이 놓여있다는 표시를 board[i] = j 의 1차원배열 형태로 표현하는 것이다. 

 

예시로 N = 4일 때, 흐름을 살펴보면 

 

1.  row = 0일 때,  첫 번째 row의 0~N-1열까지 퀸을 다 놓고 다음 열을 확인한다. (첫 번째 행에는 모든 열에 다 놓을 수 있다.)

 

2.  row = 1일 때,  두 번째 row의 0~N-1열까지 탐색한다. 이 때, 퀸을 놓을 수 있는지에 대해 검사가 필요하다.  그것을 pruning 함수로 구현하고 이를 확인한다. 확인할 때는 모든 행을 다 확인하는 것이 아닌 현재 row 이전까지의 행만 확인한다. 그 이유는 퀸을 위의 행부터 놓기 때문에 현재 탐색하는 행 아래는 볼 필요가 없기 때문이다. 

board[i] == board[row]

는 세로방향에 놓인 퀸이 있는지 확인하는 코드이다. row = 1이므로 i는 0만 확인한다. 

또한,

abs(board[row]-board[i]) == abs(row-i)

는 대각선에 위치한 퀸이 있는지 확인하는 코드이다. 오른쪽 대각선과 왼쪽 대각선 모두를 확인하기 위해 abs를 사용했고 (x1,y1), (x2,y2)가 있을 때 x2-x1 과 y2-y1이 같다면 대각선에 위치한다. 라는 개념을 사용한 것이다.

 

모든 행과 대각선에 퀸이 놓여져있지 않다면 row+1을 검사한다.

 

3.  row가 2일때와 3일때는 위의 과정과 똑같다.

 

4.  row가 3일때 놓을 수 있는 경우에 대해 row+1을 진행하는데 이 때가 row == N인 경우다.

따라서 정답 카운트를 세준다.

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline


N = int(input())
answer = 0
board = [0]*N

def pruning(row):
    for i in range(row):
        if board[i] == board[row] or abs(board[row]-board[i]) == abs(row-i):
            return False
    return True

def nQueen(row):
    global answer,board
    if row == N: # N개의 퀸을 다 놓은 경우 정답 카운트
        answer += 1
    else:
        for i in range(N): # N개의 col에 대해
            board[row] = i
            if pruning(row):
                nQueen(row+1)

nQueen(0)
print(answer)