백준 15684 사다리 조작

이 문제는 주어진 사다리 형태에서 가로 사다리를 최대 3개까지 추가해서(그 중에 최소) i번째 사다리가 i번째에 도달하는 형태를 만들 수 있는지 찾는 문제입니다. 따라서 각 경우 i번째에 도달하는지 검사를 하는 함수와 각각 0~3번 사다리를 추가하는 함수를 실행시켜 되는 경우가 있는지 확인해 주면 됩니다. 이때 연속되게 다리를 놓는것은 불가능하므로 현재 보는 구간과 이전 구간 이후 구간에 사다리가 없는지 모두 확인 한뒤 그렇다면 다리를 놓으면 됩니다. 

 

즉 다리를 0~3개 까지 추가하는 함수를 실행시킨뒤 그함수가 다리를 추가시켰을때 i번째 사다리가 i번째에 도달 한다면 그 사다리를 추가시킨 횟수가 답이 됩니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int ladder[350][350];
int N,M,H;

bool check() { //i번째 i번이 나오는지 검사
    for(int i = 1; i <= N; i++) {
        int cur = i;
        for(int j = 1; j <= H; j++) {
            if(cur < N && ladder[j][cur] == 1) { //오른쪽 연결이면 이동
                cur++;
            }
            else if(cur > 0 && ladder[j][cur-1] == 1) { //왼쪽 연결이면 왼쪽
                cur--;
            }
        }
        if(cur!=i) {
            return false;
        }
    }
    return true;
}

bool select(int x, int y, int cnt) { //0개~3개 까지 사다리 추가해보기

    if(cnt == 0) {
        if(check()) return true;
        else return false;
    }

    for(int i = x; i <= N; i++) {
        for(int j = 1; j <= H; j++) {
            if(i==x && j < y) continue;

            if(ladder[j][i] == 1 || ladder[j][i-1] == 1 || ladder[j][i+1] == 1) continue;

            ladder[j][i] = 1;
            if((select(i, j, cnt-1))) return true;
            ladder[j][i] = 0;

        }
    }
    return false;
}

int main(void) {

    cin >> N >> M >> H;

    for(int i = 0; i < M; i++) {
        int a,b; cin >> a >> b;
        ladder[a][b] = 1; // b와 b+1 세로선 사이를 a번째 가로 영역 연결
    }

    if(select(1,1,0)) {
        cout<<0;
    }
    else if(select(1,1,1)) {
        cout<<1;
    }
    else if(select(1,1,2)) {
        cout<<2;
    }
    else if(select(1,1,3)) {
        cout<<3;
    }
    else cout<<-1;
    return 0;
}