[백준] 15684번 사다리 조작 - 파이썬/백트래킹

https://www.acmicpc.net/problem/15684

1차 풀이

import sys
sys.setrecursionlimit(10**6)


N,M,H = map(int,input().split())

start=[]
end = []

for i in range(M):
    a,b=map(int,input().split())
    start.append([a,b])
    end.append([a,b+1])

axislist = []
ans_list = []

for i in range(H):
    for j in range(N-1):
        if [i+1,j+1] not in start and [i+1,j+1] not in end and [i+1,j+2] not in start:
            axislist.append([i+1,j+1])

def sadari(x,y):

    while True:
        if x>H:
            return y

        if [x,y] in start:
            x+=1
            y+=1
            continue

        elif [x,y] in end:
            x+=1
            y-=1
            continue

        else:
            x+=1


def dfs(depth,cnt,array,check_num):

    if check_num[0]:
        return

    temt = []
    print(start)
    for i in range(N):
        check = sadari(1,i+1)
        if check != i+1:
            break
        else:
            temt.append(check)

    if temt == [i for i in range(1,N+1)]:
        check_num[0]=True
        ans_list.append(cnt)
        print('answer')
        return cnt

    if depth==3:
        return

    for i in range(len(axislist)):
        if i not in array:
            if axislist[i] in end or axislist[i] in start:
                continue
            elif [axislist[i][0],axislist[i][1]+1] in start or [axislist[i][0],axislist[i][1]+1] in end:
                continue
            else:
                start.append(axislist[i])
                end.append( [axislist[i][0],axislist[i][1]+1] )
                array.append(i)
                dfs(depth+1,cnt+1,array,check_num)
                start.pop()
                end.pop()
                array.pop()

check_num = [False]
array = []
dfs(0,0,array,check_num)

if ans_list:
    print(ans_list[0])
else:
    print(-1)

사다리 결과를 체크해서 True or False를 반환하는 sadari라는 함수를 만들었다.

가능한 좌표를 백트래킹하면서 sadari 함수의 결과를 체크하는 식으로 풀었으나 시간초과가 발생했다.