백준 9663번: N-Queen (Python, PyPy3)

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

접근

체스에서 퀸은 가로, 세로, 대각선 방향으로 끝까지 이동할 수 있다. 즉, N개의 퀸을 체스판 위에 올려놓았을 때, 서로 가로, 세로, 대각선 방향으로 겹치면 안된다.

처음에는 list를 이용하여 N*N 배열의 리스트를 만들고 퀸 한개를 놓을 때마다 놓인 위치의 좌표를 이용하여 가로, 세로, 대각선 방향의 칸들을 지운 후 다음 퀸을 놓는 백트래킹 방식을 사용했는데, 수가 커질 수록 시간이 매우 늘어나 시간안에 들기가 어려웠다. 퀸들이 서로 공격하지 못하게 하기 위해서는 같은 줄(가로줄이던, 세로줄이던)에 있을 수 없는데, 이를 이용할 수 있었다. 요소의 개수가 N인 list를 이용하여 각 요소는 해당 열의 퀸의 위치를 표시하도록 하였다. (퀸은 한개의 열에 한개만 있을 수 있으므로)

또한 해당 행에 퀸이 존재하는지를 표시하는 list를 이용하고, 서로 대각선 방향으로 겹치는지 체크하는 함수를 이용하였다.

퀸을 한개씩 추가로 놓을 때마다 해당 위치에 퀸이 위치할 수 있는지를 체크하고, 놓을 수 있으면 놓고 다음 퀸의 위치를 탐색한다. N*N 체스판에 N개의 퀸 놓기를 성공하면 count를 한개 추가하고 탐색을 계속한다.

코드

import sys

n = int(sys.stdin.readline())
board = [0] * n
ans_count = 0
visited = [False] * n  # n번째 열에 퀸이 있는지를 표시하는 list


def check(x):  # 기존에 있는 퀸들과 대각선 방향으로 겹치는 퀸이 있는지를 확인
    for i in range(x):
        if abs(board[x] - board[i]) == x - i:
            return False
    return True


def n_queen(x):
    global ans_count
    if x == n:
        ans_count += 1
        return
    for i in range(n):
        if visited[i]:  # i번째 열에 퀸이 있을 경우 continue
            continue

        board[x] = i
        if check(x):
            visited[i] = True
            n_queen(x + 1)
            visited[i] = False


n_queen(0)
print(ans_count)

더 생각해 볼 것?

체스판의 크기를 배열 한개로 줄이고, list를 이용하여 check 함수에서 for문 순환하는 동안 계산을 최대한 줄이려고 했는데도 Python으로 통과하지 못하여 PyPy3으로 돌렸더니 성공하였다.

계산이 느린 Python으로 제한 시간 안에 통과할 수 있는 방법이 있는지 좀더 고민해봐야겠다.

(제가 제시한 코드가 가장 효율적인 코드가 아님을 참고해주세요.)