[ 백준 15684 ] 사다리 조작 (C++) - DFS, BruteForce

---

🔗 문제 링크

15684번: 사다리 조작

---

💡 문제 풀이 및 해석

1. 경우의 수가 크지 않으므로 BruteForce로 풀 수 있을 것이라 생각했다.
2. 일단, 0개를 설치한 경우는 반드시 조건에 성립하므로 예외처리해 준다. (안 해줘도 상관없다.)
3. DFS 방식으로 사다리를 설치하면 브루트 포스하게 풀 수 있다. (이게 최선인지는 아직 모르겠다.)
4. 설치할 다리의 개수를 모두 설치했을 때, 이 방식이 정답인지 확인하고 아니면 다음 경우의 수로 넘어간다.
5. 정답이 나올 때까지 3번-4번을 반복한다.
6. 모두 정답이 아닐 때, 답이 없는 것이므로 -1을 출력한다.

---

⭐️ 정답 코드 및 설명

#include<iostream>

using namespace std;

int N, M, H;
int Next[35][15]; // 1이면 오른쪽으로 -1이면 왼쪽으로
bool Answer;
void init() {
    cin >> N >> M >> H;
    if (M == 0) Answer = true;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Next[a][b] = 1; // 내려갈 때, 오른쪽으로 1칸이동
        Next[a][b + 1] = -1; // 내려갈 때, 왼쪽으로 1칸이동
    }
}

bool isAnswer() { // 이것이 정답인가?
    for (int x = 1; x <= N; x++) {
        int sx = x, sy = 1; // 이 지점에서 내려감 sx 가 세로축이라 보면됌.
        for (int y = 1; y <= H; y++) {
            sx += Next[sy][sx]; // 좌우 혹은 그대로 유지
            sy++; // 아래로 한칸
        }
        if (sx != x) return false; // 하나라도 같은 번호가 아니라면 false
    }
    return true; // 모두 같은 번호로 내려왔으면 정답이다.
}

void sol(int cnt) {
    if (cnt == 0) {
        if (isAnswer()) {
            Answer = true;
        }

        return;
    }
    // DFS 방식으로 한다.
    for (int x = 1; x <= N - 1; x++) {
        if (Answer) break;
        for (int y = 1; y <= H; y++) {
            if (Answer) break;
            if (Next[y][x] == 0 && Next[y][x + 1] == 0) { // 다리가 설치 가능할 때, 설치해보자
                Next[y][x] = 1; Next[y][x + 1] = -1;
                sol(cnt - 1);
                Next[y][x] = 0; Next[y][x + 1] = 0;
            }
        }
    }
    return;
}

int main() {

    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    init();
    if (Answer) {
        cout << 0;
        return 0;
    }

    int cnt = 0;

    // 4개 이상이면 틀린 답이라고 문제에 나와 있다. 나는 이 부분을 못봐서 최대 갯수까지 돌리다가 시간초과가 계속 났다.
    while (4 > cnt) {
        sol(cnt);
        if (Answer) break;
        cnt++;
    }
    if (Answer) cout << cnt << "\n";
    else cout << -1;

    return 0;
}

---

🤔 문제 후기

일단, 문제를 제대로 읽지 않아서,,, 시간초과로 2번이나 틀렸고,,, 다시 한번 문제의 조건을 꼼꼼하게 읽자고 다짐했다. 문제 자체는 브루트 포스하게 푼다면, 생각할 것이 많은 문제는 아니었는데, 솔직히 시간이 될까?라는 생각이 많았다. 그도 그럴 것이,,, 처음에는 최대 3개까지만 설치해 보라는 조건을 읽지 못해서 조합문제인데 최대 300개의 경우의 수 중에서 내가 고르는 것인데, 2초 안에 절대 안 된다는 것을 알았는데,,, 다른 풀이가 생각나지 않아 일단 해봤는데, 역시나 시간초과였다. 그러다가 도저히 모르겠어서 구글링을 했는데 사람들 풀이가 하나같이 4 이상이면 -1을 리턴한다 해서 문제를 다시 읽어봤고, while 문의 조건만 고치니 바로 통과했다. 다시 한번,,, 문제를 제대로 읽자고 느꼈다.