백준 9663 파이썬 - N-Queen

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

9663번: N-Queen

문제

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

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

코드

import sys
n = int(sys.stdin.readline())
arr = [0 for _ in range(16)]
result = 0
def check(num):
    for i in range(1, num):
        if arr[num] == arr[i] or abs(arr[num] - arr[i]) == num - i:
            return False
    return True
def dfs(count):
    global result
    if count > n:
        result += 1
    else:
        for i in range(1, n + 1):
            arr[count] = i
            if check(count):
                dfs(count + 1)
dfs(1)
print(result)

풀이

시간 제한 10초를 맞추기가 어려운 문제다. arr배열의 크기를 n+1로 하면 시간 초과가 되고 pypy로 제출해야 성공하는 것 같다. 우선 check함수는 놓을 수 있는 곳인지 확인하는 함수이다. arr배열은 각 행을 의미하고 count를 1씩 증가시키며 dfs함수를 호출하고 count가 입력값인 n보다 크면 다 들어갔다는 뜻이므로 result를 1씩 늘려준다. 함수가 다 돌고나서 result를 출력한다.