[PYTHON] 백준 9663 - N-Queen

성능 요약

메모리: 216816 KB, 시간: 30580 ms

분류

브루트포스 알고리즘, 백트래킹

문제 설명

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

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

입력

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

출력

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

#https://www.acmicpc.net/problem/9663
#N-Queen
#9663

import sys
input = sys.stdin.readline

n = int(input())
row = [0] * n

# for i in range(x): 
#     if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
#         return False
# return True

def check(x, row):
    for i in range(x): 
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True

def dfs(x, n, row):
    result = 0

    if n == 1:
        return 1
    elif n == 2 or n == 3:
        return 0
    
    if x == n:
        return 1
    
    else:
        for i in range(n):
            row[x] = i
            if check(x, row):
                result = result + dfs(x + 1, n, row)

    return result

print(dfs(0, n, row))

이문제를 풀때 이유없는 시간초과를 경험함