[백준]사다리조작(second)

https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

#완전탐색을 이용해 최소 값(단계)을 찾는 문제  : 원래는 if len==M : Return 방식으로 길이를 도달했을 때 종료를 해주었다.

그래서 for문을 통해 끝점을 늘려주면서 if문 안에서 처리를 해주었었다..

하지만, 멍청한 방식이었다... ㅠㅠ

그냥 길이에 상관없이 완전탐색을 하면서 바로바로 진행을 해주고 최대 제한깊이 까지 갔을 때 return을 해주면 된다..

그리고 이 방식은 끝없이 깊어지는 것을 방지하기 위해 가지치기가 필수이다. (시간초과 발생방지)

#include <cstdio>
 
int n, m, h, ans=4;
bool a[30][10];
 
bool ladder() {
    for (int i=0; i<n; i++) {
        int k=i;
        for (int j=0; j<h; j++) {
            if (a[j][k]) k += 1;
            else if (k > 0 && a[j][k-1]) k -= 1;
        }
        if (i != k) return false;
    }
    return true;    
}
 
void solve(int cnt, int x) {
    if (ans <= cnt) return; //가지치기. 이미 최소를 구하면 뒤는 노필요
    if (ladder()) {
        ans = cnt;
        return;
    }
    if (cnt == 3) return; //3개의 사다리를 했으므로 더 할필요 X
    for (int i=x; i<h; i++) {
        for (int j=0; j<n-1; j++) {
            if(!a[i][j]) {
                a[i][j] = 1;
                solve(cnt+1, i);
                a[i][j] = 0;
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d", &n, &m, &h);
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x-1][y-1] = 1; //왼 -> 오 , 의 사다리라고 ㅐㅇ각
    }
    solve(0, 0);
    printf("%d\n", ans == 4 ? -1 : ans);
    return 0;
}