백준 15684 사다리 조작 python

사타리 게임 구현 문제이다.
기본적으로 DFS를 통해서 해결했지만 시간초과 문제가 있어, 백트래킹을 여러번 시도해 봤는데 pyhon3는 통과가 안 됐고 pypy3만 통과할 수 있었다.

📜 문제 바로 가기 : 사다리 조작

제출코드

파이썬

import sys
input = sys.stdin.readline

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

# -1 : 왼쪽 연결, 1 : 오른쪽 연결
arr = [[0] * (H+1) for _ in range(N+1)]

for _ in range(M):
    # b번과, b+1 번을 a번째 가로선에서 연결
    a, b = map(int, input().split())
    arr[b][a] = 1
    arr[b+1][a] = -1

def recur(s, lastA, lastB):
    global ans

    if s >= ans:
        return

    if check() == True:
        ans = s
        return

    for a in range(lastA, N):
        for b in range(lastB+2, H+1):
            # a번과 a+1번을 b번 가로에서 연결
            if arr[a][b] == 0 and arr[a+1][b] == 0 :
                arr[a][b] = 1
                arr[a+1][b] = -1
                recur(s+1, a, b)
                arr[a][b] = 0
                arr[a+1][b] = 0
        lastB = -1

        
                
def check():
    for i in range(1, N):
        now = i
        for j in range(1, H+1):
            if arr[now][j] == 1:
                now += 1
            elif arr[now][j] == -1:
                now -= 1
        
        if now != i:
            return False
    
    return True

ans = 4
recur(0, 1, -1)

if ans == 4:
    print(-1)
else:
    print(ans)

---

접근방법

내가 사용한 백트래킹은 2가지이다.

1. a번과 a+1번을 b 가로줄에서 연결했다면 다음 b+1 번 가로줄에는 다리를 놓지 않는다.
이유는 a, a+1번을 연결하는데 b, b+1 가로줄에 연달아 다리가 놓여있다면 사다리타기 특성상 다리를 놓기 전의 위치와 똑같아진다. 따라서 a, a+1 지점을 연결하는 다리를 연달아 놓는 것은 의미가 없다.

2. a번 연결의 b번 가로줄까지 봤다면 다음은 a번 연결의 b가로줄 이전은 생각하지 않는다.
조합이기 때문에 당연한 부분이다. 그런데 지금까지는 for문이 하나였기에 마지막 인덱스만 고려하면 됐지만 이 문제는 2중 for문으로 들어가기 때문에 다른 처리가 필요하다.

왜냐하면 a번 b가로줄에 다리를 놓고 그냥 a, b를 다음 함수에서 고려해보면 a번 b+1 부터 고려가되겠지만 a+1 번도 b+1 부터 확인하는 불상사가 일어난다.
이부분에 대한 처리로 두번째 for문이 끝날때마다 두번째 시작점을 초기화시켜주는 로직을 하나 추가 했다. (여기에서는 lastB = -1 )