[백트래킹][완전탐색] 15684 사다리 조작 c++구현

목차

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

문제

 

 

문제 구현 방향

가로축과 세로축의 범위를 생각하면 300C3정도로 완전탐색 가능한 범위이다.

또한 문제의 조건을 보면 정답이 3보다 크면 -1을 출력하라는 것을 보아 백트래킹으로 가지치기를 하면 된다.

 

 

문제 풀이

인덱스 그대로 생각해 주면 된다. 오히려 복잡하게 생각할 필요가 없다.

visit[][]이라는 이차원 배열을 만든 뒤 사다리 조건에 맞추어 사다리를 추가해 주고 조건 체크를 해주면 된다.

 

 

코드 구현

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

using namespace std;

int N, M, H;

int visit[32][32] = { 0 };
int minN = 999;

//사다리가 제자리로 가는지 조건 체크
int check() {
    for (int i = 1; i <= N; i++) {
        int start = i;
        int cur = i;
        //인덱스 범위는 항상 주의해주자
        for (int h = 1; h <= H; h++) {
            if (visit[h][cur]) {
                cur += 1;
                continue;
            }
            if (cur - 1 >= 1) {
                if (visit[h][cur - 1])
                    cur -= 1;
            }
               
        }
        
        if (cur != start)
            return 0;
     
    }
    return 1;
}

//백트래킹으로 사다리 조건에 맞추어 추가
void backT(int here, int cnt) {
  
    if (cnt > 3) {
        return;
    }
    if (check()) {
        minN = min(cnt, minN);
        return;
    }
    for (int i = here; i <= H; i++) {
        for (int j = 1; j <= N - 1; j++) {
            if (visit[i][j])
                continue;
            if (j - 1 >= 1) {
                if (visit[i][j - 1])
                    continue;
            }
            if (j + 1 <= N - 1) {
                if (visit[i][j + 1])
                    continue;
            }
            visit[i][j] = 1;
            backT(i, cnt+1);  //cnt++로 해주면 틀린다! 주의 
            visit[i][j] = 0;  //원상복구 해주자
           
        }
    }
}

int main() {
    int r, c;
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        cin >> r >> c;
        visit[r][c] = 1;
    }
    backT(1, 0);
    if (minN == 999)
        cout << -1;
    else
        cout << minN;
    return 0;
}