[BOJ] N-Queen(9663) - PYTHON

N * N 크기의 체스판이 있을 때, N개의 퀸을 놓을 수 있는 경우의 수를 구하는 문제다. N개의 퀸은 서로 공격할 수 없어야 한다.

시간 복잡도: O(N!) (??)

(각 행마다 1개의 Queen을 놓을 수 있으며 첫 행에 놓을 수 있는 자리는 N개이고 행이 커질수록 위의 행에서 1~3개만큼 가능한 자리가 줄어든다. 이를 수식으로 어떻게 나타내야 할지 모르겠어서 최소 1개는 줄어들기 때문에  N!이라고 썼다.)

9663번: N-Queen

---

풀이과정

체스판에서 Queen은 위, 아래, 대각선 이동이 가능하다. 7 X 7 체스판의 중앙에 Queen이 있을 때 움직일 수 있는 공간은 다음과 같다.

빨간색 사각형이 색칠된 위치로 이동할 수 있다.

Queen은 우선 좌우로 움직일 수 있기 때문에 체스판에 N개의 Queen을 서로 공격할 수 없게 놓으려면 각 행에 1개의 Queen만 놓을 수 있다.
따라서 크기가 N인 1차원 배열 matrix를 선언하고  인덱스=> 행의 번호, 값=> 행에서 Queen의 위치로 나타낼 수 있다.
위 예시에서는 matirx[3] = 3으로 퀸의 위치를 나타낼 수 있다.

이렇게 첫 행부터 위치할 수 있는 Queen을 채워나가면서 마지막 행까지 Queen을 놓으면 가능한 경우가 생긴 것이다. 따라서 재귀 함수를 통해 첫 행부터 N이 올 수 있는 위치를 채워나가면서 문제를 해결한다.

예시)
7 X 7 행에서 0~1행까지 각 퀸이 다음과 같이 존재한다고 가정해보자.

0~1행까지 Queen을 채운 상태

그렇다면 2번 행에서 존재할 수 있는 위치는 윗 방향, 왼쪽 대각선 윗 방향, 오른쪽 대각선 윗 방향에 Queen이 존재하는 위치를 제외한 1,4,5,6이다. 즉 현재 위치에서 위에 있는 행들을 조사해 위, 대각선 방향으로 Queen이 존재하지 않는다면 Queen을 놓을 수 있다.

이렇게 각 행마다 재귀함수를 통해 윗 방향 행에서의 Queen의 위치를 참조해서 Queen을 놓을 수 있는 위치에 놓은 후 다음 행으로 넘어가면서 문제를 해결한다.

출처: 위키피디아

---

코드

def nQueen(row, N, matrix):
    global answer
    if row == N:
        answer += 1
        return
    else:
        check = [0] * N
        for i in range(row):
            check[matrix[i]] = 1
            if 0 <= row - i + matrix[i] < N:
                check[row - i + matrix[i]] = 1
            if 0 <= matrix[i] - row + i < N:
                check[matrix[i] - row + i] = 1
        for i, temp in enumerate(check):
            if temp == 0:
                matrix[row] = i
                nQueen(row + 1, N, matrix)
 
 
N = int(input())
answer = 0
matrix = [0] * N
nQueen(0, N, matrix)
print(answer)
 

 

주석추가

def nQueen(row, N, matrix):
    global answer  # 정답값을 Update하기 위해 Global변수임을 명시
    if row == N:  # 현재위치가 N이면 (체스판에 N개의 Queen을 모두 놓았다면)
        answer += 1  # 정답 + 1
        return
    else:
        check = [0] * N  # 현재 행에 놓을 수 있는 Queen의 위치를 저장하기 위한 배열 (값이 0이면 놓을 수 있고, 1이면 놓을 수 없다.)
        for i in range(row):  # 현재 행의 앞의 행들에 대해서
            check[matrix[i]] = 1  # 같은 열에 있는 위치에는 놓을 수 없다
            if 0 <= row - i + matrix[i] < N:  # 위쪽 행들의 각 Queen에서 오른쪽 아래 대각선 방향으로 내려왔을 때 현재 행에서의 위치가 체스판 안에 있다면
                check[row - i + matrix[i]] = 1  # 해당 위치에는 Queen을 놓을 수 없다.
            if 0 <= matrix[i] - row + i < N:  # 위쪽 행들의 각 Queen에서 왼쪽 아래 대각선 방향으로 내려왔을 때 현재 행에서의 위치가 체스판 안에 있다면
                check[matrix[i] - row + i] = 1  # 해당 위치에는 Queen을 놓을 수 없다.
        for i, temp in enumerate(check):  # check의 index와 value를 가져와
            if temp == 0:  # 값이 0이면(행에서 index위치에 Queen을 놓을 수 있다면)
                matrix[row] = i # 해당 위치에 Queen을 놓고
                nQueen(row + 1, N, matrix) # 다음 행으로 이동
 
 
N = int(input())
answer = 0  # 정답 값
matrix = [0] * N  # N 크기의 1차원 배열을 생성 index: 행의 값 value: 해당 행에서의 Queen 위치
nQueen(0, N, matrix)  # 0행부터 Queen을 채우기
print(answer)
 

---

참고

입력이 1~14의 범위로 주어지므로 각 N에 대해 가능한 경우의 수를 계산해보면 아래와 같은 결과가 나온다.

N에따른 정답값

즉 N이 6 이상일 때부터 가능한 경우의 수가 기하급수적으로 증가하며, 계산량도 똑같이 증가한다.

---

채점 결과

처음에 python3을 통해 채점했는데 시간 초과가 떴다. 각 행에서 놓을 수 있는 위치를 계산하는 과정을 좀 더 효율적으로 바꾸고 pypy3로 채점했더니 통과했다.