이번 문제는 백트레킹을 통해 해결하였다. 우선 사다리가 겹치거나 만나면 안되기 때문에 이를 체크할 리스트 ladders를 2차원 리스트로 선언하였다. 그리고 입력받은 사다리에 해당하는 좌표 ladders[a][b]를 1로 갱신해주었다. 여기서 주의할 점은 a, b에서 무조건 자신의 오른쪽으로 사다리를 뻗었다는 사실을 기억해야 한다는 점이었다.

백트레킹 함수에 num이라는 사다리 수의 제한을 두고, 모든 좌표를 순회하며 현재 좌표의 왼쪽, 오른쪽, 현재 좌표에 사다리가 없을 경우에 ladders[a][b]를 1로 갱신하고, 백트레킹 함수를 재귀 호출 하였다. 그리고 ladders[a][b]를 다시 0으로 갱신시키는 백트레킹을 수행하였다. 그리고 가지치기를 위해 while문을 통해 ladders[j][i-1]이나 ladders[j][i]에 사다리가 있을 때까지 j를 증가시켰다.

그리고 cnt가 num과 같아졌을 경우에 check_result함수를 통해 모든 좌표에서 사다리를 내려와 값이 시작점의 값과 같은지 확인하고 같다면 answer를 cnt로 갱신시켜주었다.

Code

n, m, h=map(int, input().split())
ladders=[[0 for _ in range(n+1)] for _ in range(h+1)]
for _ in range(m):
    a, b=map(int, input().split())
    ladders[a][b]=1
answer=1e9
def check_result():
    for i in range(1, n+1):
        cur=i
        for j in range(1, h+1):
            if ladders[j][cur]==1:
                cur+=1
            elif ladders[j][cur-1]==1:
                cur-=1
        if cur!=i:
            return False
    return True
def find_way(num, cnt):
    global answer
    if answer!=1e9:
        return
    if num==cnt:
        if check_result():
            answer=cnt
        return
    for i in range(1, n):
        for j in range(1, h+1):
            if ladders[j][i-1]==0 and ladders[j][i+1]==0 and ladders[j][i]==0:
                ladders[j][i]=1
                find_way(num, cnt+1)
                ladders[j][i]=0
                while j<h:
                    if ladders[j][i-1] or ladders[j][i+1]:
                        break
                    j+=1
for i in range(4):
    find_way(i, 0)
    if answer!=1e9:
        break
if answer==1e9:
    answer=-1
print(answer)