글 읽기 - 로컬에서 돌려도 10분 이상 돌아갑니다

3846chs 4년 전 0

백트래킹 이렇게 푸는 거 아닌가요?

N 이 8 이하일 때는 빠르게 답이 나오는데(답은 맞습니다)

N 이 9 이상일 때부터 급속하게 느려집니다.(답도 맞는 것 같습니다.)

특히 N 이 14일 때는 10분 이상 걸리네요..

다들 이렇게 푸시지 않았나요...?

import copy


def update_board(row, col, board):
    board = copy.deepcopy(board)
    if not board[row][col]:
        return -1
    
    # 가로, 세로
    for i in range(N):
        board[i][col] = False
    for j in range(N):
        board[row][j] = False
    
    # 대각선
    a = row + col
    for p in range(a+1):
        if 0 <= p < N and 0 <= a-p < N:
            board[p][a-p] = False

    if row >= col:
        b = row - col
        for q in range(N):
            if 0 <= q < N and 0 <= b+q < N:
                board[b+q][q] = False
    else:
        b = col - row
        for q in range(N):
            if 0 <= q < N and 0 <= b + q < N:
                board[q][b+q] = False

    return board


def func(row, brd):
    global cnt
    if row == N:
        cnt += 1
        return
    for col in range(N):
        new_board = update_board(row, col, brd)
        if new_board == -1: # invalid
            continue
        else:
            func(row+1, new_board)
    return



N = int(input())
cnt = 0
b = [[True for j in range(N)] for i in range(N)]
func(0, b)
print(cnt)