글 읽기 - N-Queen 시간초과 파이썬

wndlswo12 4년 전 0

왜 시간초과나오는지 모르겠습니다.

제 코드 26번째 줄 if canUseIt : 에서 사용가능한 경우만 다음 r에 대해 고려했기 때문에 잘 pruning 한 거 아닌가요?

from sys import stdin

input = stdin.readline

n = int(input())

queenQue = [] #만든 이유 : 이전 퀸들에 대해 고려해야 하므로.

count = 0

def CountQueen(r,c,q_num): 
    global count

    if q_num == n : #만약 queenQue내에 있는 갯수가 n개가 된다면
        count += 1 #count+=1 해주고
        queenQue.pop() #집어넣었던거 지우기.(for문 돌렸으니 다음 c에 대해 고려 함.)
        return

    for c in range(n):#모든 c에 대해 탐색.(r행의 모든 열에 대해)
        canUseIt = True
        for pre_r,pre_c in queenQue: #filter라 생각하면 됨. 기존 퀸과 곂치느냐?
            if pre_c == c or (abs(pre_r-r)==abs(pre_c-c)):
                canUseIt = False #겹친다면 break!
                break

        if canUseIt: #겹치지 않아서 r,c를 써먹을 수 있다면
            queenQue.append((r,c))#r,c를 queen목록에 넣고
            CountQueen(r+1,0,q_num+1) #다음 행에 대해서 판단하구 queen목록 수 +1

    if queenQue: #r행에 대한 c를 모두 탐색했음에도 없으면 직전꺼 지우기.(for문 돌렸으니 이전에서 다음 c에 대해 고려함)
        queenQue.pop()
        
CountQueen(0,0,0)

print(count)

djm03178 4년 전 3

이 문제를 Python 3로 백트래킹으로 통과하기는 매우 어렵습니다. 최적화를 그냥 잘 하는 정도가 아니라, 아주 능숙해야 합니다.

wndlswo12 4년 전 0

pypy3로 제출해보니 정말이네요... 56ms 통과한 사람들이 있길래 얼마나 잘푼건가 했더니 정답만 제출이네요;

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

N-Queen 시간초과 파이썬

wndlswo12 4년 전 0

djm03178 4년 전 3

wndlswo12 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말