[C++] 15684: 사다리 조작

흐으음...

🖍️ 겪은 문제

• 백트래킹으로 푸는 방법을 아예 몰라서 1~3중까지 for문으로 구현해 풀려고 하였으나, 코드가 길어지다보니 로직에 오류가 생겼음.
• 그래서 문제를 풀지 못했다 ㅜㅜ 복습을 할 때 참고하려고 가장 마음에 드는 풀이를 보고 글을 적는다.

🔍 해결 방법

• DFS 백트래킹을 적용함.
• check() 함수는 열에 대해 순회하며
  • 현재 위치에 true가 있으면 다리를 타고 우측으로 이동하므로 pos를 ++, 
  • 현재 위치 좌측에 true가 있으면 다리를 타고 좌측으로 이동하므로 pos를 --해서
  • 최종 pos가 시작한 열과 동일하면 조건을 만족한다고 판단함.

📇 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

int N, M, H;
int minCnt = 4;
vector<vector<bool>> ladder(31, vector<bool>(11, false));

bool check() {
    for (int i=1; i<=N; i++) {
        int pos = i;

        for (int j=1; j<=H; j++) {
            if (ladder[j][pos]) pos++;
            else if (ladder[j][pos-1]) pos--;
        }

        if (pos != i) return false;
    }

    return true;
}

void DFS(int h, int cnt) {
    if (cnt >= minCnt) return;
    if (check()) minCnt = cnt;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> H;

    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b; // 1-base
        ladder[a][b] = true;
    }

    DFS(1,0);

    if (minCnt > 3) cout << -1;
    else cout << minCnt;

    return 0;
}