15684. 사다리 조작

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

15684번: 사다리 조작

 

풀이

필요 알고리즘: 백트래킹

 

필자는 문제를 처음 보고 사다리를 어떻게 구현해야 하나 당황스러웠지만, 결국 2차원 배열을 활용하여 어렵지 않게 구현할 수 있었다. 사다리 타기를 구현한 뒤에는 가로선을 추가하는 경우를 백트래킹으로 전부 확인하면 된다.

 

필자가 사다리를 구현한 방식은 다음과 같다. 아래는 문제에서 제시한 사다리이다.

사다리를 표현하는 2차원 배열 ladder를 선언한다. 이 배열의 행이 가로선, 열이 세로선인데, 구현의 편의를 위해 0번째 인덱스는 여백으로 두고 1번째 인덱스부터 시작하도록 하였다. 각 배열의 칸에는 가로선이 어느 방향으로 향해 있는지를 기록한다. 가로선이 오른쪽으로 향하면 1, 왼쪽으로 향하면 -1, 가로선이 없으면 0이다.

 

다음으로 사다리 타기를 구현해야 한다. 문제에 따르면 j번째 사다리를 타면 j번째 위치로 도달하는지를 확인해야 하는데, 이는 다음과 같은 절차로 확인 가능하다. 

1. ladder[1][j]의 값을 확인한다. (가로선이 존재하는지 확인)
2. ladder[1][j]이 1이면 j의 값을 1 증가시키고, -1이면 1 감소시킨다. (가로선이 있으면 그것을 따라 인접한 세로선으로 이동)
3. ladder[2][j] ~ ladder[M][j]에 대하여 위 과정을 반복한다. (세로선을 따라 내려가며 가로선 확인 및 이동을 반복)
4. 모두 확인을 끝낸 뒤의 j와 최초의 j의 값이 같은지를 확인한다. (j번째 사다리를 타서 j번째 위치로 도달했는지를 확인)
5. N개의 세로선 모두가 두 값이 같다면 사용한 가로선의 개수를 출력한다.

요약하자면, 가로선의 이동을 j 값의 증감으로 표현하여 사다리 타기를 구현할 수 있다.

 

사다리 조작을 위한 가로선 추가의 경우, ladder[i][j]의 값이 0이면 ladder[i][j] = 1, ladder[i][j + 1] = -1으로 놓고 지우는 식으로 백트래킹을 하면 된다. 방식 특성상 맨 마지막 세로선(N번째 세로선)을 확인해서 가로선을 놓는 일이 없도록 주의한다. 또한, 백트래킹 시 ladder[i][j]를 확인해서 가로선을 놓으면 ladder[i][j + 1]은 -1이 써져 확인하는 의미가 없으므로, 이를 건너뛰고 ladder[i][j + 2](또는 ladder[i + 1][1])를 확인한다면 실행 시간을 줄일 수 있을 것이다.

 

시간 복잡도

최대 \(H(N-1)\)개의 가능한 위치에서 가로선을 1~3개 놓고, 각각에 대해 최대 \(HN\)칸의 2차원 배열을 전부 확인하며 사다리가 올바른 위치로 도달하는지 확인한다. 따라서 시간 복잡도는 \(HN\left({H(N-1) \choose 1}+{H(N-1) \choose 2}+{H(N-1) \choose 3}\right)\)이다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, H, a, b, ans = 4;
int ladder[31][11];

bool isValidLadder() {
    for(int i = 1; i <= N; i++) {
        int st = i;
        for(int j = 1; j <= H; j++) {
            if(ladder[j][st] != 0) st += ladder[j][st];
        }
        
        if(i != st) return false;
    }
    
    return true;
}

void backtrack(int cnt, int r, int c) {
    if(cnt > 3) return;
    
    for(int i = r, j = c; i <= H; i++) {
         do {
             if(ladder[i][j] != 0 || ladder[i][j + 1] != 0) continue;
             ladder[i][j] = 1; ladder[i][j + 1] = -1;
             
             if(isValidLadder()) {
                 ans = min(ans, cnt);
                 ladder[i][j] = 0; ladder[i][j + 1] = 0;
                 continue;
             }
             
             if(j + 2 >= N) backtrack(cnt + 1, i + 1, 1);
             else backtrack(cnt + 1, i, j + 2);
             ladder[i][j] = 0; ladder[i][j + 1] = 0;
        } while(++j < N);
        
        j = 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M >> H;
    for(int i = 0; i < M; i++) {
        cin >> a >> b;
        ladder[a][b] = 1; ladder[a][b + 1] = -1;
    }
    
    if(isValidLadder()) ans = 0;
    else backtrack(1, 1, 1);
    
    if(ans == 4) cout << -1;
    else cout << ans;
    return 0;
}