15684: 사다리 조작

• 사다리가 놓여진 위치 표시를 board 2차원 리스트로 해주었다
  -> board[i][j]에서 i는 사다리 가로선의 행번호, j는 사다리 시작점의 열번호

backtracking(depth, x, y)

• depth는 추가한 사다리의 개수임
• x, y 위치에서부터 사다리를 하나씩 추가로 설치하면서 backtracking을 진행함
• board[i][j], board[i][j+1] 위치에 사다리가 없고, j>0일 때 board[i][j-1]인 경우 외의 경우에 사다리를 i, j 위치에 설치할 수 있음
  -> 재귀호출을 할 때, 해당 세로선 위치 + 2 부터 사다리를 추가할 수 있기 때문에 backtracking(depth+1, i, j+2) 형식으로 재귀호출을 진행해야함
• depth가 3보다 큰 경우 return
• is_complete()가 True라면 result를 갱신해주고 return

is_complete()

• 현재 board의 상태에서 문제의 조건에 맞게 도착점에 도착하는 지를 check하는 함수

구현이 어려운 backtracking 문제였다

import sys
from collections import deque

def is_complete():
    for j in range(N): #모든 세로선을 순회
        check = j
        for i in range(H):
            if board[i][check]:
                check += 1
            elif check > 0 and board[i][check-1]:
                check -= 1
        if check != j: #같은 세로선 위치로 도착하지 않은 경우 False 반환
            return False
    return True

def backtracking(depth, x, y): #depth는 추가한 사다리의 개수
    global result

    if depth > 3:
        return
    elif is_complete():
        result = min(result, depth)
        return

    for i in range(x, H):
        if i == x: startY = y
        else: startY = 0
        for j in range(startY, N - 1):
            if not board[i][j] and not board[i][j+1]:
                if j > 0 and board[i][j-1]:
                    continue
                board[i][j] = True
                backtracking(depth + 1, i, j+2)
                board[i][j] = False


N, M, H = list(map(int, sys.stdin.readline()[:-1].split())) #N: 세로선 개수, M: 가로선 개수, H: 가로선을 놓을 수 있는 위치 개수

board = [[False] * N for _ in range(H)]
if M == 0:
    print(0); exit()

for m in range(M):
    tmp = list(map(int, sys.stdin.readline()[:-1].split()))
    tmp[0] -= 1; tmp[1] -= 1
    board[tmp[0]][tmp[1]] = True #tmp[0]:가로선의 행번호, tmp[1]:시작점의 열번호

result = 4
backtracking(0, 0, 0)
if result < 4:
    print(result)
else:
    print(-1)