사다리 조작

참고 : https://baby-ohgu.tistory.com/3
python3는 시간초과, pypy3로만 통과

코드

def check():
    for j in range(n):
        now = j
        for i in range(h):
            if board[i][now] == 1:
                now += 1  # 오른쪽으로
            elif now - 1 >= 0 and board[i][now - 1] == 1:
                now -= 1  # 왼쪽으로
        if now != j:
            return False
    return True


def dfs(count, x, y):
    global answer

    if check():
        answer = min(answer, count)
        return

    if count == 3 or answer <= count:
        # count == 3 : 다음 스택에서 count가 4가 됨
        # answer <= count : 지금까지 찾은 최소 사다리수(answer)보다 
        # 현재의 사다리수(count)가 많으면, 의미없는 경우의 수이다.
        # 최소 사다리수를 구해야하기 때문이다.
        return

    for i in range(x, h):
        k = y if i == x else 0
        # 현재 위치 (x,y)에서는 그 다음 오른쪽 사다리를 체크
        # 행이 변경되었을 경우, 해당 행(i)의 맨 처음 사다리(0)부터 체크
        for j in range(k, n - 1):
            if board[i][j] != 1 and board[i][j + 1] != 1:  
            # i,j 위치에서 오른쪽에 사다리가 없을 경우
                if j - 1 >= 0 and board[i][j - 1] == 1:  
                # i,j 위치에서 왼쪽에 사다리가 있다면 (접한다)
                    continue
                board[i][j] = 1  # 사다리 설치
                dfs(count + 1, i, j + 2)  
                # 사다리 개수(count)에 1증가, 
                # 현재 위치에서 오른쪽으로 2칸 이동(i, j+2)
                board[i][j] = 0  # 사다리 제거


n, m, h = map(int, input().split())
board = [[0 for _ in range(n)] for _ in range(h)]

if m == 0:
    print(0)
    exit()

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

answer = 4
dfs(0, 0, 0)
print(answer if answer <= 3 else -1)

접근방식

가능한 경우의 수를 구한 뒤 체크하는 방식은 시간이 오래걸린다.
-> 재귀를 활용하여 가능한 + 불가능한 모든 경우의 수를 체크하고
-> 재귀 종료 조건을 활용하여 불가능한 경우를 걸러내고, 가능한 경우에 대해서만 답에 반영한다.
-> 백트래킹