문제

링크

복습 요망!!

풀이

이해하기 굉장히 어려운 문제였다. 다른 사람의 풀이를 참고하여 겨우 풀었지만, 다음날 다시보면 처음보는 것처럼 낯설다.

사다리를 적절하게 만들어 사다리 시작번호와 도착번호가 같게 해야하는 문제이다. 모든 사다리를 만들면 시간 초과가 발생할 수 있어, 적절히 백트래킹을 하여 경우의 수를 줄이면서 답을 찾아야한다.

추후 정리

코드

import sys

input = sys.stdin.readline
N, M, H = map(int, input().split())
ladder = [[0] * N for _ in range(H)]
ans = 4

for i in range(M):
    r, c = map(int, input().split())
    ladder[r - 1][c - 1] = 1


def move():
    for n in range(N):
        start = n
        for h in range(H):
            if ladder[h][start]:  # 우측이동
                start += 1
            elif start > 0 and ladder[h][start - 1]:  # 좌측이동
                start -= 1
        if start != n:
            return False
    return True


def dfs(cnt, x, y):
    global ans
    if ans <= cnt:
        return
    if move():
        ans = min(ans, cnt)
        return
    if cnt == 3:
        return
    for i in range(x, H):
        k = y if i == x else 0
        for j in range(k, N - 1):
            if ladder[i][j]:
                j += 1
            else:
                ladder[i][j] = 1
                dfs(cnt + 1, i, j + 2)
                ladder[i][j] = 0


dfs(0, 0, 0)
print(ans if ans < 4 else -1)

참고 : https://rebas.kr/790