파이썬 백준 9663번: N-Queen

문제

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

9663번: N-Queen

 

풀이

이차원 배열 possible_table로 queen을 놓을 수 있는 위치를 탐색한다.

possible_table의 값은 모두 0으로 초기화 한다. 

queen이 놓인 위치의 왼쪽 대각선 아래, 오른쪽 대각선아래, 아래의 값들에 1을 더한다. (make_False)

이후 다음 행에서 queen을 놓을 수 있는 곳을 탐색한다.

해당 행의 탐색이 끝나면 queen이 영향을 줬던 자리들의 1을 뺀다 (make_True)

import sys

def make_False(i,j):
    temp_i=i
    temp_j=j
    while(0<=temp_i<N and 0<=temp_j<N):
        possible_table[temp_i][temp_j] +=1  # 왼쪽아래
        temp_i += 1
        temp_j -= 1
    temp_i = i
    temp_j = j
    while (0 <= temp_i < N and 0 <= temp_j < N):
        possible_table[temp_i][temp_j] +=1  # 오른쪽아래
        temp_i += 1
        temp_j += 1
    for k in range(i+1,N):
        possible_table[k][j] +=1  # 아래

def make_True(i, j):
    temp_i = i
    temp_j = j
    while (0 <= temp_i < N and 0 <= temp_j < N):
        if possible_table[temp_i][temp_j] > 0:
            possible_table[temp_i][temp_j] -=1 # 왼쪽아래
        temp_i += 1
        temp_j -= 1
    temp_i = i
    temp_j = j
    while (0 <= temp_i < N and 0 <= temp_j < N):
        if possible_table[temp_i][temp_j]>0:
            possible_table[temp_i][temp_j] -=1  # 오른쪽아래
        temp_i += 1
        temp_j += 1

    for k in range(i+1,N):
        if possible_table[k][j] > 0:
            possible_table[k][j] -=1  # 아래

def backtracking(i,j):
    if i>=N :
        global num
        num+=1
        return
    for j in range(N):
        if possible_table[i][j]==0:
            make_False(i,j)
            backtracking(i+1,j)
            make_True(i, j)
    return

N=int(sys.stdin.readline())
possible_table=[]
for i in range(N):
    possible_table.append([0] * N)

num=0
backtracking(0, 0)
print(num)

 

 

😣 덧)

pypy로 제출했다. python으로는 시간초과를 벗어나는 방법이 없는것 같다. 

찾아보니 python으로 통과하려면 1~15까지의 정답을 모두 써놓고 출력하는 방법밖에 없다고..

import sys
result = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184]
print(result[int(sys.stdin.readline())])