백준 15684 사다리 조작 (C++)

15684번: 사다리 조작

개인적으로 문제 이해가 좀 힘들었던 문제였다. 사다리에서 조작에 필요한 가로선 개수를 찾는 문제인데 우선 조건이 두가지 주어진다.

1. 두 가로선이 연속하거나 서로 접하면 안 된다.
2. 가로선은 점선 위에 있어야 한다.

사다리 위에서 조작에 필요한 위치를 찾는 것이므로 백트래킹을 이용하면 되고, DFS를 위의 두가지 조건을 예외처리하며 돌면 된다. isRight함수에서 사다리 전체를 돌아보며 시작 위치와 도착 위치가 일치하는지 확인하여 답을 구해주었다.
처음 답을 제출했을 때는 9퍼에서 넘어가지 않으면서 시간초과가 떠서 굉장히 곤란했었다. 다른 분들의 풀이를 참고해보니 while (!A[i][j - 1] && !A[i][j + 1]) i++; 와 같은 코드를 추가하여 의미없는 구간을 스킵하여 속도를 올려주고 있었다. 대단한 것 같다.

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;

int N, M, H, res = INF;
bool A[31][11]; // H, N;

bool isRight() {
    for (int j = 1; j <= N; j++) {
        int x = j;
        for (int i = 1; i <= H; i++) {
            if (A[i][x]) x++;
            else if (A[i][x - 1]) x--;
        }
        if (x != j) {
            return false;
        }
    }

    return true;
}

void dfs(int depth, int count) {
    if (depth == count) {
        if (isRight()) {
            res = min(res, depth);
        }
        return;
    }

    for (int j = 1; j <= N - 1; j++) {
        for (int i = 1; i <= H; i++) {
            if (A[i][j] || A[i][j - 1] || A[i][j + 1]) continue;
            A[i][j] = true;
            dfs(depth, count + 1);
            A[i][j] = false;

            while (!A[i][j - 1] && !A[i][j + 1]) i++;
        }
    }
}

void solution() {
    for (int i = 0; i < 4; i++) {
        dfs(i, 0);
    }
   
    if (res == INF) res = -1;
    
    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> H;

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        A[a][b] = true;
    }

    solution();

    return 0;
}