4. [re] 사다리 조작

백준

1. DFS

# n (열), m (가로선 개수), h (행)
import sys
input = sys.stdin.readline
n, m, h = map(int, input().split())
ladder = [[0] * n for _ in range(h)]
answer = sys.maxsize

for _ in range(m):
    a, b = map(int, input().split()) #행, 열
    ladder[a - 1][b - 1] = 1

def check():
    for i in range(n):
        k = i
        for j in range(h):
            if ladder[j][k]:
                k += 1
            elif k > 0 and ladder[j][k-1]:
                k -= 1
        if i != k:
            return False
    return True

def dfs(count, x, y):
    global answer
    if answer <= count: #최솟값 이상은 돌필요 x
        return
    if check():
        answer = min(answer, count)
    if count == 3:
        return 
    for i in range(x, h): #행
        if i == x: #재귀의 경우(같은 행)에는 열 값 유지
            k = y
        else:
            k = 0
        for j in range(k, n - 1): #열
            if ladder[i][j]:
                j += 1
            else:
                ladder[i][j] = 1
                dfs(count + 1, i, j + 2)
                ladder[i][j] = 0

dfs(0,0,0)

if answer < 4:
    print(answer)
else:
    print(-1)