BOJ 15684 - 사다리 조작

문제

백준 온라인 저지 - 15684번

풀이 과정

DFS 와 백트래킹 을 활용한 최적화가 필요한 탐색 문제입니다.

이때 사다리의 위치를 검사하는 과정에서 인덱스 범위에 대한 고려를 안해주기 위해 board 양쪽에 padding 을 추가했습니다.
이렇게 안하면 양쪽 사다리 위치 인덱스가 board 를 벗어나는지에 대한 조건문에 추가해줘서 코드가 복잡해집니다.
사다리를 2차원 배열로 표현했으므로 각 시작점에서 타고 내려올때는 왼쪽, 오른쪽에서 만나는 경우를 고려해줘야 합니다.
주의할 점은 수평 방향으로 이동했을 경우에는 바로 한칸 밑으로 전진시켜줘야합니다. (안그러면 무한 루프에 빠집니다.)

DFS 를 수행하는 과정에서 만약 만족하는 조합을 찾았을 경우에는 이후 탐색을 수행하지 않고
바로 True 를 반환하도록 해서 불필요한 탐색을 줄였습니다.

코드

import sys

N, M, H = list(map(int, sys.stdin.readline().split()))
ladders = []
for i in range(M):
    ladders.append(list(map(int, sys.stdin.readline().split())))


def match(board):
    for start in range(1, N+1):
        cur = [0, start]

        while cur[0] < H:
            # 왼쪽에서 만날 경우
            if board[cur[0]][cur[1]]:
                cur = [cur[0], cur[1] + 1]
            # 오른쪽에서 만날 경우
            elif board[cur[0]][cur[1]-1]:
                cur = [cur[0], cur[1] - 1]

            cur[0] += 1

        if cur[1] != start:
            return False
    return True


def dfs(board, depth, goal):
    if depth == goal:
        return match(board)

    ret = False
    for r in range(H):
        for c in range(1, N):
            if board[r][c] != 1 and board[r][c-1] != 1 and board[r][c+1] != 1:
                board[r][c] = 1
                ret = dfs(board, depth+1, goal)
                if ret:
                    return True
                board[r][c] = 0
    return ret


def solution():
    # board 초기화
    board = [[0 for _ in range(N+2)] for _ in range(H)]  # 양쪽에 padding
    for ladder in ladders:
        board[ladder[0]-1][ladder[1]] = 1

    for i in range(4):
        if dfs(board, 0, i):
            return i

    return -1


print(solution())