글 읽기 - 파이썬 시간초과 , !!!! 고수분들 제발 코린이 살려주세용

awhtjddn1 1년 전 0

파이썬 시간초과 뜨는데 접근 방식이 잘못된건지 아니면 아예 틀린건지 어느 부분을 고치면 되는건지 백트래킹 문제를 처음 풀어봐서 감이 안오네요 알려주시면 정말 감사합니다. !!

dx = [1,-1,0,0,1,1,-1,-1]
dy = [0,0,1,-1,1,-1,1,-1]
def dfs(num):
    global count , graph , N
    if len(graph)==N :
        count +=1
        return
    if num > (N*N) :
        return 
    for i in range(num,(N*N)) :
        check_ok = True 
        x = i//N+1
        y = i%N+1

        for j in range(8):
            nx = x
            ny = y     
            while check_ok :
                nx = nx +dx[j]
                ny = ny +dy[j]
                if nx < 1 or nx > (N) or ny <1 or ny >(N) :
                    break
                if [nx,ny] in graph :
                    check_ok =False
                    break

            if check_ok == False :
                break
            
        if check_ok :
            graph.append([x,y])
            #print(graph)
            dfs(i+1)
            graph.pop()

N = int(input())
count = 0 
graph =[]
dfs(0)
print(count)

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

문제

문제

출처

ICPC

파이썬 시간초과 , !!!! 고수분들 제발 코린이 살려주세용

awhtjddn1 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말