백준 15684 사다리조작

문제 주소 : www.acmicpc.net/problem/15684

15684번: 사다리 조작

문제 확인

 

dfs 형태로 문제풀이

최소 개수를 찾는 문제이기 때문에 놓을 사다리 수를 0개부터 4개까지 순서대로 탐색합니다.

 

풀이

 

놓을 사다리 수를 0개부터 탐색하며 가능한 경우를 찾는 즉시 출력합니다.

dfs, 의미없는 탐색을 줄이기 위해 세로 방향 탐색 시 의미가 중복되는 사다리는 넘어갑니다.
//while(!a[i][j - 1] && !a[i][j + 1]) i++;

 

코드

#include <cstdio>
int N, M, H, m = 4;
bool a[31][11];
bool ch() {//시작점과 끝점이 같은지 확인
    for (int i = 1; i <= N; i++) {
        int t = i;
        for (int j = 1; j <= H; j++) {
            if (a[j][t]) t++;
            else if (a[j][t - 1]) t--;
        }
        if (t != i) return false;
    }
    return true;
}
void dfs(int cn, int mc) {//
    if (m != 4)return;//0개부터 탐색을 하기 때문에 찾는 즉시 모든 dfs 종료
    if (mc == cn) {
        if (ch())
            m = m > cn ? cn : m;
        return;
    }
    for (int j = 1; j < N; j++) {
        for (int i = 1; i <= H; i++) {
            if (a[i][j] || a[i][j + 1] || a[i][j - 1])continue; //붙은 사다리 체크
            a[i][j] = 1;
            dfs(cn + 1, mc);
            a[i][j] = 0;
            while (!a[i][j - 1] && !a[i][j + 1]) i++; //의미가 중복되는 사다리는 넘어감
        }
    }
}
int main() {
    scanf("%d%d%d", &N, &M, &H);
    for (int i = 0, x, y; i < M; i++) {
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    for (int i = 0; i < 4; i++) { //최대로 놓을 사다리 수를 0개부터 체크
        dfs(0, i);
        if (m != 4) {
            printf("%d", m);
            break;
        }
    }
    if (m == 4)printf("-1");
 
}