사다리 조작

문제

https://www.acmicpc.net/problem/15684

길어서 링크로 대체

브루트포스로 모든 경우의 수를 계산해보아야 한다.

사다리를 조작해 i번째 시작점에서 출발하는 것이 i 번째에 도착하게 만들어야 한다.

1. check 함수를 만들어 현재 사다리 모양으로 i번째 좌표가 i번째 도착지에 도착할 수 있는지 확인한다.

2. 도착할 수 있다면 그대로 프로그램을 종료하고, 불가능하다면 사다리 조작이 필요하다는 의미이므로, 사다리를 조작하기 시작한다.

3. 반복문과 백트래킹을 이용한 조작을 한다. 우선 최소한의 횟수로 사다리를 조작했을 때 가능한지를 확인해야 하기 때문에, 1개로만 사다리를 설치했을 때 가능한지 확인해야 한다.

4. 반복문을 돌면서 사다리를 설치할 수 있는 경우에는 설치하는 함수를 실행한다. 백트래킹을 이용할 경우, 반복문을 돌기도 전에 계속 사다리 개수를 늘리기 때문에, 모든 반복문을 한 바퀴 돌 때까지 백트래킹을 제한하는 변수를 설정한다.

n, m, h = map(int, input().split())
bridge = [[False] * n for _ in range(h)] # 사다리를 배열에 기록
for _ in range(m):
    a, b = map(int, input().split())
    bridge[a - 1][b - 1] = True
ans = 4


def check():
    for start in range(n): # 가로
        k = start
        for i in range(h): # 세로 내려옴
            if bridge[i][k]: # 배열에 bridge 있으면 오른쪽 이동
                k += 1
            elif k > 0 and bridge[i][k - 1]:
                k -= 1
        if start != k:
            return False
    return True


def bf(cnt, x, y): # 시작 점
    global ans
    if check():
        ans = min(ans, cnt) #
        return
    elif cnt == 3 or ans <= cnt:
        return
    for i in range(x, h): # 내가 사다리를 놓을 곳 y 값
        k = y if i == x else 0
        for j in range(k, n - 1): #
            if not bridge[i][j] and not bridge[i][j + 1]:
                bridge[i][j] = True
                bf(cnt + 1, i, j + 2)
                bridge[i][j] = False

def solution():
    if m == 0:
        print(0)
        return
    bf(0, 0, 0)
    print(ans if ans < 4 else -1)
solution()