[PyPy] [DFS] 백준 15684 사다리 조작

문제

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

15684번: 사다리 조작

코드

n,m,h=map(int,input().split())
graph=[[False]*(n+1) for _ in range(h+1)]
array=[]

for _ in range(m):
    a,b=map(int, input().split())
    graph[a][b]=True

for i in range(1,h+1):
    for j in range(1,n):
        if not graph[i][j] and not graph[i][j-1] and not graph[i][j+1]:
            array.append([i,j])

def check():
    for i in range(1,n+1):
        cur=i
        for j in range(1,h+1):
            if graph[j][cur-1]:
                cur-=1
            elif graph[j][cur]:
                cur+=1
        if cur != i:
            return False
    return True

def dfs(depth,a_i):
    global answer

    if answer<=depth:
        return
    if check():
        answer=depth
        return

    for i in range(a_i,len(array)):
        x,y=array[i]
        if not graph[x][y-1] and not graph[x][y+1]:
            graph[x][y]=True
            dfs(depth+1,i+1)
            graph[x][y]=False

answer=4
dfs(0,0)

print(answer if answer<4 else -1)