[15674] 사다리 조작

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

오늘 문제는 사다리 조작이다.

사다리 타기 게임을 시뮬레이션 하는 문제이다.

내가 임의로 몇 개의 가로 선을 추가해서 i번 째 사다리를 i번 사다리로 통과하게 만들어야 한다.

만약 추가해야하는 가로 선이 3개가 넘어가거나 어떻게 가로 선을 놓아도

i번 째 사다리가 i번 사다리로 통과하지 못한다면 -1를 출력하고

가로 선을 추가해 위 조건을 만족시킬 수 있다면 그 가로 선의 개수의 최소 값을 출력하는 문제이다. (0개도 가능하다)

문제 해결 아이디어는 이전의 문제들 처럼 완전 탐색을 통해 풀었다.

가로 선은 최대 3개만 설치해야하고 사다리의 최대 개수와 높이가 각각 10, 30이므로

완전탐색을 이용해도 시간내에 충분히 가능하다.

먼저 인풋의 사다리의 정보를 이 차원 배열을 만들어 가로 선의 시작 점 1, 끝 점 -1로 초기화 한다.

그 후 벡터를 하나 만들어서 가로 선이 놓일 수 있는 지점인

현재 지점 값이 0이면서 같은 가로 위치의 다음 사다리의 값이 0인 지점를 모두 넣어준다.

그 다음 가로 선을 0개 놓았을 때부터 3개 놓았을 때까지의 완전탐색을 for문을 통해 진행해 주고

만약 조건을 만족하는 경우가 있다면 바로 종료하면 된다. (0개부터 시작이니 먼저 걸리는게 가장 최소 값)

3개까지 다 진행했음에도 만족하는 경우가 나오지 않는다면 -1를 출력하면 된다.

끝.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n, m, h, cnt, mini;
int arr[35][15], temp[35][15];
bool check[330];
vector<pair<int, int> > vt;
 
bool func() {
    for (int i = 1; i <= n; i++) {
        int here = i;
        for (int j = 1; j <= h; j++) {
            if (temp[j][here] == 0) continue;
            else if (temp[j][here] == 1) here++;
            else if (temp[j][here] == -1) here--;
        }
        if (here == i) continue;
        else return 0;
    }
    return 1;
}
 
void dfs(int num, int r, int i) {
    if (num >= cnt) {
        if (r == 0) {
            if (func()) {
                mini = min(mini, i);
            }
        }
        return;
    }
    if (r>0) {
        int x = vt[num].first;
        int y = vt[num].second;
        if (temp[x][y] == 0 && temp[x][y + 1] != 1) {
            check[num] = 1;
            temp[x][y] = 1;
            temp[x][y + 1] = -1;
            dfs(num + 1, r - 1, i);
            temp[x][y + 1] = 0;   
            temp[x][y] = 0;
            check[num] = 0;
        }
 
    }
    dfs(num + 1, r, i);
}
 
int main() {
    scanf("%d %d %d", &n, &m, &h);
    for (int i = 0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        arr[x][y] = 1;
        arr[x][y + 1] = -1;
    }
    cnt = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j<n; j++) {
            if (!arr[i][j] && !arr[i][j+1]) {
                vt.push_back({ i, j });
                cnt++;
            }
        }
    }
    mini = 987654321;
    for (int i = 0; i<4; i++) {
        memset(check, 0, sizeof(check));
        memcpy(temp, arr, sizeof(arr));
        dfs(0, i, i);
        if (mini == i) break;
    }
    if (mini == 987654321)
        puts("-1");
    else
        printf("%d\n", mini);
 
    return 0;
}