[백준-15684] 사다리 조작

15684번: 사다리 조작

이거는 약간 구현에 신경써야 하는 문제이다.

여러번 풀어보는 것도 나쁘지 않다고 생각한다.

일단 하나씩 다 돌아보는 단순한 브루트포스 알고리즘으로 풀리는 문제이다. 다만 각 가로줄들을 데이터로 잘 표현하여 탐색을 돌리는 구현이 깔끔하게끔 짜야하는 문제가 있다.

각 가로줄을 일일이 저장하는 것이 아닌 특정 점에서 밑으로 내려올 수 있다 없다 로 가로줄을 판단할 수 있다.

예를 들어 check[3][4]=1 이라면 (3,4) 에서 사다리 밑으로 내려올 수 있다는 의미가 될 수 있다.

이를 이용해 check[x][y], check[x][y-1], check[x][y+1] 이 3개의 값을 비교하여 1인 경우 dfs 탐색을 돌리는 식으로 로직을 구성하면 문제를 풀 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

using namespace std;

int n, m, h; 
int arr[100][100];
int check[100][100];
int _min = 1000000;
bool isok() {
    int cx;
    for (int i = 1; i <= n; i++) {
        cx = i;
        for (int j = 1; j <= h; j++) {
            if (check[j][cx] == 1) cx = cx + 1;
            else if (check[j][cx-1] == 1) cx = cx - 1;
        }
        if (cx != i) return false;
    }
    return true;
}
void dfs(int x, int cnt) {
    if (cnt >= 4) {
        return;
    }
    if (isok()) {
        _min = min(_min, cnt);
        return;
    }

    for (int i = x; i <= h; i++) {
        for (int j = 1; j < n; j++) {
            // check[x][y] = 1 
            if (check[i][j] == 1) continue;
            if (check[i][j-1] == 1) continue;
            if (check[i][j+1] == 1) continue;

            check[i][j] = 1;
            dfs(i, cnt + 1);
            check[i][j] = 0;
        }
    }
}
int main() {
    int a, b;

    cin >> n >> m >> h;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        check[a][b] = 1;
    }
    dfs(1, 0); 
    if (_min == 1000000) cout << -1;
    else cout << _min;

    return 0;
}