[C++] 백준 15684번 | 사다리 조작

사다리 조작

15684번: 사다리 조작

---

✍🏻 풀이

처음에는 인접한 번호를 잇는 가로선이 각 줄마다 짝수개면 각 번호에 도착하게 될 줄 알았는데,

예제 5를 보고 잘못 생각했다는 걸 깨달았다.

5 8 6
1 1
2 2
3 3
4 4
3 1
4 2
5 3
6 4

그렇다고 사다리를 놓는 모든 경우의 수를 탐색하자니, 시간 초과가 날 것이다.

이 문제를 해결하기 위해서는 정답이 3보다 큰 값이면 -1을 출력한다. 라는 조건을 잘 사용해야 한다.

이 조건은 사다리를 0, 1, 2, 3개를 놓았을 때의 경우의 수만 고려하면 된다는 것을 의미한다.

 

1. main 함수에서 사다리 개수의 최댓값을 0, 1, 2, 3개로 각각 DFS 함수를 돌려준다.
2. DFS 함수에서는 빈 공간에 사다리 개수의 최댓값만큼 사다리를 놓고, ladderGame 함수를 호출하여 해당 사다리가 유효한지 검증한다.
3. 해당 배치가 유효하다면 바로 사다리의 개수를 출력하고 함수를 종료시킨다.
   이 때, 이후의 경우의 수를 탐색하지 않는 이유는 main 함수에서 사다리의 최댓값을 0부터 3까지 순차적으로 넣어줬기 때문이다.

풀고나니 간단한 문제였다.

---

✅ Accept Code

// baekjoon 15684

#include <bits/stdc++.h>

using namespace std;


int N, M, H;
int ladder[31][11];
vector<int> lines;
int ans = INT_MAX;

bool ladderGame() {
    for (int j = 1; j <= N; j++) {
        int a = 1;
        int b = j;
        while (a <= H) {
            if (ladder[a][b]) b++;
            else if (ladder[a][b - 1]) b--;
            a++;
        }
        if (b != j) return false;
    }
    return true;
}

void DFS(int maxDepth, int cnt) {
    if (cnt == maxDepth) {
        if (ladderGame()) {
            cout << maxDepth;
            exit(0);
        }
        return;
    }

    for (int j = 1; j <= N; j++) {
        for (int i = 1; i <= H; i++) {
            if (ladder[i][j] || ladder[i][j - 1] || ladder[i][j + 1]) continue;
            ladder[i][j] = 1;
            DFS(maxDepth, cnt + 1);
            ladder[i][j] = 0;

            while (!ladder[i][j - 1] && !ladder[i][j + 1]) i++;  // 사다리 놓을 수 있을 때까지 i++

        }
    }
}


int main() {
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        ladder[a][b] = 1;
    }
    for (int i = 0; i < 4; i++) {
        DFS(i, 0);
    }
    if (ans == INT_MAX) cout << -1;
    else cout << ans;
    return 0;
}