[Back Tracking] 백준 9663번 : NQueen - Python 파이썬

 

 

생각하기

각 row에는 하나의 퀸만 있고

각 col에는 하나의 퀸만 있어야 한다

그리고 왼쪽 아래 대각선과 오른쪽 아래 대각선을 모두 고려해야 함

오른쪽 아래 대각선은 row idx - col idx + N -1 이 모두 같은 칸이고

왼쪽 아래 대각선은 col idx - row idx 이 모두 같은 칸이다 

 

이를 고려하여 recursive를 돌리면 된다 

처음에는 plus_mem 과 minus_mem을 리스트로 선언하여 append하였지만 이는 시간초과를 가져오는 결과를 보였다

import sys
import copy
input = sys.stdin.readline

N = int(input())

cnt = 0

def search(row, col_mem, plus_mem, minus_mem):
    global cnt
    
    if row == N:
        cnt += 1
        return

    for col in range(0, N):
        if col_mem[col] == False:
            if (row + col) in plus_mem:
                continue
            if (col-row) in minus_mem:
                continue
            n_col_mem = copy.deepcopy(col_mem)
            n_col_mem[col] = True
            n_plus_mem = copy.deepcopy(plus_mem)
            n_plus_mem.append(row+col)
            n_minus_mem = copy.deepcopy(minus_mem)
            n_minus_mem.append(col-row)

            search(row+1, n_col_mem, n_plus_mem, n_minus_mem)

col_mem = [False] * N
plus_mem = []
minus_mem = []

search(0, col_mem, plus_mem, minus_mem)
print(cnt)

매개변수로 리스트를 넘기는 문제도 있지만

for i in minus_men 을 하면서 탐색시간이 n이 더해진다는 것이 시간적으로 부담이되었다

따라서 차라리 하나의 전역 배열을 선언하고

recursion을 빠져나올 때, False 화 하기로 한다

 

import sys
import copy
input = sys.stdin.readline

N = int(input())

plus_mem = [False] * 100
minus_mem = [False] * 100
col_mem = [False] * N


def search(row, cnt):
    
    if row == N:
        cnt += 1
        return cnt

    for col in range(0, N):
        if col_mem[col] == False and plus_mem[col+row] == False and minus_mem[row-col+N-1] == False:
            
            col_mem[col] = True
            plus_mem[row+col] = True
            minus_mem[row-col+N-1] = True

            cnt = search(row+1, cnt)

            plus_mem[row+col] = False
            minus_mem[row-col+N-1] = False
            col_mem[col] = False

    return cnt


print(search(0, 0))