BOJ 15684 · 사다리 조작

알고리즘 분류 : 브루트 포스, 백트래킹  

사다리를 적절히 만들어서 사다리 타기를 해야하는 문제다. 가로줄은 최대 3개까지 놓을 수 있고, 최솟값을 출력하면 된다. 출발한 사다리 번호(세로줄)와 도착한 사다리 번호가 모두 같아야 사다리를 제대로 탄 것이다. 가능한 사다리를 모두 만들면 시간 초과될 수 있으므로, 적절히 백트래킹을 하여 경우의 수를 줄여야 한다.

• 주어진 입력을 통하여 H*N 사이즈의 사다리를 만든다.
• A번 세로줄과 A+1번 세로줄의 사이에 B번 가로줄로 연결한다면, 사다리 [A][B]를 연결(1)한다.
• 아래 그림을 확인.

• 재귀 함수를 이용하여 가능한 사다리를 만든다.
• 사다리에 가로줄을 만들 때, 가로줄은 연속해서 만들지 않아도 되는 것에 유의한다.
• 만약 현재 위치가 (i, j)이고, 사다리가 연결되어 있다면(1), (i, j+2)로 점프한다.
• 현재 위치가 (i, j)이고, 사다리가 연결되어 있지 않다면(0), 현재 위치 (i, j)에 가로줄을 하나 만들고 j+2로 점프하여 재귀 함수를 호출한다.
• 가로줄을 최대 3개까지만 만든다.
• 만약 정답을 구했으면, 정답 보다 많이 가로줄을 만들 필요가 없으므로, 재귀 함수 호출을 하지 않는다.

• 사다리를 하나 만들 때마다, 제대로 연결된 사다리인지 확인한다.
• 1번 세로줄부터 N번 세로줄까지 모두 확인해야 한다.
• 현재 위치 (i, j)에 사다리가 연결되어 있으면(1), 오른쪽(i, j+1)으로 꺾는다. 
• 현재 위치 (i, j)에 사다리가 연결되어 있지 않으면(0), 왼쪽(i, j-1)이 1인지 확인하고 맞으면 왼쪽(i, j-1)으로 꺾는다.
• 현재 위치에서 사다리를 한 칸 내려간다. (i+1, j)
• 위 과정을 가로줄이 H에 도달할 때까지 반복한다.

---

C++ 소스코드

#include <cstdio>

int n, m, h, ans=4;
bool a[30][10];

bool ladder() {
    for (int i=0; i<n; i++) {
        int k=i;
        for (int j=0; j<h; j++) {
            if (a[j][k]) k += 1;
            else if (k > 0 && a[j][k-1]) k -= 1;
        }
        if (i != k) return false;
    }
    return true;    
}

void solve(int cnt, int x, int y) {
    if (ans <= cnt) return;
    if (ladder()) {
        if (ans > cnt) ans = cnt;
        return;
    }
    if (cnt == 3) return;
    for (int i=x; i<h; i++, y=0) {
        for (int j=y; j<n-1; j++) {
            if (a[i][j]) {
                j += 1;
            } else {
                a[i][j] = 1;
                solve(cnt+1, i, j+2);
                a[i][j] = 0;
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &h);
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x-1][y-1] = 1;
    }
    solve(0, 0, 0);
    printf("%d\n", ans < 4 ? ans : -1);
    return 0;
}

---

PyPy3 소스코드

ans = 4
n, m, h = map(int, input().split())
a = [[0]*n for _ in range(h)]
for _ in range(m):
    x, y = map(int, input().split())
    a[x-1][y-1] = 1

def ladder():
    for i in range(n):
        k = i
        for j in range(h):
            if a[j][k]:
                k += 1
            elif k > 0 and a[j][k-1]:
                k -= 1
        if i != k:
            return False
    return True

def solve(cnt, x, y):
    global ans
    if ans <= cnt:
        return
    if ladder():
        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 a[i][j]:
                j += 1
            else:
                a[i][j] = 1
                solve(cnt+1, i, j+2)
                a[i][j] = 0

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

✓ Python 3로 제출하면 시간 초과가 나오므로, PyPy3로 제출해야 한다.

---

참고

• 백준 온라인 저지 : BOJ 15684