[jungol] 1889 : N Queen -python code

문제
체스에서 queen은 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있다.

즉 다음과 같은 체스판에서 queen이 X라고 표시된 위치에 있을 때,

그 다음 queen이 움직여 갈수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.

N X N 크기의 정방형 체스판이 주어졌다.

우리는 거기에 N개의 queen을 배치하려고 하는데, 모든 queen들은 서로 잡아먹을 수 없어야 한다.

그렇다면 queen들을 어떻게 배치해야만 할까?

가능한 모든 경우의 개수를 출력한다.

입력형식
queen의 수 N(1≤N≤13)을 입력 받는다.

출력형식
N X N의 체스판에서 N개의 queen들이 서로 잡아먹지 않는 위치로 놓을 수 있는 방법의 수를 출력한다.

처음에 무작정 for문으로 처리했을 때는 시간초과가 떴다.

## 시간초과
def put_Q(y,x):
    for r in range(N):
        table[r][x]+=1
    for c in range(N):
        table[y][c]+=1
    for z in range(-N,N,1):
        if 0<=y+z<N and 0<=x+z<N:
            table[y+z][x+z]+=1
    for z in range(-N,N,1):
        if 0<=y+z<N and 0<=x-z<N:
            table[y+z][x-z]+=1
    table[y][x]-=3

def del_Q(y,x):
    for r in range(N):
        table[r][x]-=1
    for c in range(N):
        table[y][c]-=1
    for z in range(-N,N,1):
        if 0<=y+z<N and 0<=x+z<N:
            table[y+z][x+z]-=1
    for z in range(-N,N,1):
        if 0<=y+z<N and 0<=x-z<N:
            table[y+z][x-z]-=1
    table[y][x]+=3


def f(row):
    global s
    if row==N:
        s+=1
        return
    for i in range(N):
        if table[row][i]==0:
            put_Q(row,i)
            f(row+1)
            del_Q(row,i)


N = int(input())
table = [[0 for _ in range(N)] for y in range(N)]
s=0
f(0)
print(s)

그래서 따로 리스트를 만들어 저장하여 시간초과를 해결하였다.

## 시간초과 해결
def put_Q(y,x):
    chk_x[x]+=1
    chk_y[y]+=1
    chk_Dr[x+y]+=1
    chk_Dc[y-x+3]+=1

def del_Q(y,x):
    chk_x[x]-=1
    chk_y[y]-=1
    chk_Dr[x+y]-=1
    chk_Dc[y-x+3]-=1


def f(row):
    global s
    if row==N:
        s+=1
        return
    for i in range(N):
        if  chk_x[i]+chk_y[row]+chk_Dr[row+i]+chk_Dc[row-i+3]==0:
            put_Q(row,i)
            f(row+1)
            del_Q(row,i)


N = int(input())
table = [[0 for _ in range(N)] for y in range(N)]
chk_x=[0 for x in range(N)]
chk_y=[0 for x in range(N)]
chk_Dr=[0 for x in range(2*N)]
chk_Dc=[0 for x in range(2*N)]
s=0
f(0)
print(s)