[백준][C++] 15684번: 사다리 조작 <219>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

15684번: 사다리 조작

생각의 흐름

우선 사다리 좌표계를 다음과 같이 생각하였다.

ladder[i][j] == true 는 i행 j열에 가로 사다리가 배치되어있다는 의미이다.

 

우선 isValid라는 메서드를 다음과 같이 만들었다.

bool isValid(){
    for(int col = 1; col <= N; col++){
        int nowLine = col;
        for(int row = 1; row <= H; row++){
            if(ladder[row][nowLine]) nowLine++;
            else if(ladder[row][nowLine - 1]) nowLine--;
        }
        if(nowLine != col) return false;
    }
    return true;
}

위 메서드는 사다리가 우리 문제에 조건에 부합하는지? 즉 i번째 에서 시작하면 i번째에서 끝나는지? 를 확인하는 함수이다.

 

이후 DFS 탐색을 하게되는데,

우선 1행부터 cnt값을 0으로 시작할것 이다. cnt값이 4이상이 되면 바로 탐색을 종료하면 된다. (백트래킹)

 

이후 dfs 의 depth 가 내려갈때 마다 isValid로 확인해줘야 한다.

처음에 잘못 생각하면 depth가 3이 됬을때만 isValid로 확인해줘야 한다 생각할 수 있는데,

매번 검사하여 최소의 값을 찾는것이 우리 목적이다. 

가로 사다리를 1개만 추가하고도 isValid함수 조건을 만족할수 있기 때문이다.

 

make_ladder에서 index는 가장 위로부터 얼마나 떨어져 있는지에 대한 숫자이다.

1이면 가장 위로부터 1번째 가로축, 2면 가장 위로부터 2번째 떨어진 가로축을 의미한다.

for(int i = index; i <= H; i++) {
    for(int j = 1; j <= N; j++) {
        if(ladder[i][j] == true) continue;
        if(ladder[i][j-1] == true) continue;
        if(ladder[i][j+1] == true) continue;
        ladder[i][j] = true;
        make_ladder(i, cnt+1);
        ladder[i][j] = false;
    }
}

따라서 1번부터 ~ H번 까지의 모든 가로축을 탐색하게 된다.

각 i번 가로축마다 j번째 칸을 확인하게 된다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define INF 2147000000

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

bool isValid(){
    for(int col = 1; col <= N; col++){
        int nowLine = col;
        for(int row = 1; row <= H; row++){
            if(ladder[row][nowLine]) nowLine++;
            else if(ladder[row][nowLine - 1]) nowLine--;
        }
        if(nowLine != col) return false;
    }
    return true;
}

void make_ladder(int index, int cnt) {
    if(cnt >= 4) {
        return;
    }
    if(isValid()) {
        res = min(res, cnt);
        return;
    }

    for(int i = index; i <= H; i++) {
        for(int j = 1; j <= N; j++) {
            if(ladder[i][j] == true) continue;
            if(ladder[i][j-1] == true) continue;
            if(ladder[i][j+1] == true) continue;
            ladder[i][j] = true;
            make_ladder(i, cnt+1);
            ladder[i][j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    make_ladder(1, 0);

    cout << ((res == INF) ? -1 : res) << "\n";

    return 0;
}