[백준] 사다리 조작 15684번 (c++) 구현

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

 

풀이 방법

최대 설치 사다리가 3개이므로 완전 탐색 + 구현으로 풀이했다.
설치된 사다리를 어떤 자료구조로 저장할지도 중요하다.

ladder[y][x] 배열에 설치 유무를 저장했다.  의미는 y번째 가로줄에 x번째 세로줄에서 x+1번째 세로줄로 연결된 위치이다.

 

 

작성해야 하는 함수

1. i번째 세로줄이 i번째로 가는지 체크하는 함수

2. i번째 사다리의 시뮬레이션 결과 어디로 도착할지 판단하는 함수

3. 현재 자리에 설치가 가능한지 체크하는 함수(양 옆으로 있으면 못함)

4. dfs 함수 (모든 경우를 다 체크하기 위해서) 인자로 (y, x, cnt) cnt == 사다리 설치 개수

 

완전 탐색을 위해 백트레킹을 해준다.

백트레킹을 위해 ladder배열의 초기화가 중요하다. 설치한 후 조건에 맞지 않으면 ladder배열을 다시 0으로 설정해 주어야 한다.

 

시뮬레이션 결과를 위해선 가로선의 인덱스를 늘려가며, 현재 x_idx, x_idx-1 중 사다리가 설치되어 있는 곳으로 이동하며 제일 밑까지 이동하면 된다.

 

// 유의 할 점 
// 1. 백 트레킹할 때 특정 조건으로 먼저 빠져나가는 경우에도 초기화 하기
// 2. y,

#include<iostream>
#include<memory.h>
#include<algorithm>


using namespace std;


int n, m, h;
int ladder[31][11]; // 세로, 가로 // 왼쪽 시작점의 좌표를 기준으로 한다.
//사다리를 연속해서 설치하면 안된다.
// 최대 3개를 설치할 수 있다.

int last_idx(int idx) { // 현재 i번째 위치 사다리의 마지막 위치를 결정한다.
    int y_idx = 1;
    int x_idx = idx;
    while (y_idx <= h) {
        if (ladder[y_idx][x_idx] == 1) {//오른 쪽으로 이동
            x_idx++;
        }
        else if (ladder[y_idx][x_idx-1] == 1) {//왼 쪽으로 이동
            x_idx--;
        }   
        y_idx++;
    }    
    return x_idx;
}

bool check_ladder() { // 모두가 갈 수 있는지 체크하는 함수
    //체크를 할 때 현재나 앞칸을 체크해서 사다리가 있으면 이동한다.
    for (int i = 1;i <= n;i++) {
        if (i != last_idx(i)) {
            return false;
        }
    }

    return true;
}
bool can_install(int y, int x) {
    if (ladder[y][x] == 1) return false;
    int left = max(x - 1, 1), right = min(x + 1, n-1);
    if (ladder[y][left] == 1) return false;
    if (ladder[y][right] == 1) return false;

    return true;
    
}

int dfs(int y, int x, int cnt) { // y, x에 설치하고 현재 cnt의 개수를 추가 설치했다.               
    if (!can_install(y, x)) return 987654321; //현재 위치에 사다리를 설치하지 못하는 경우
    int ret = 987654321; // 불가능한 경우 최대로 설정
    ladder[y][x] = 1; // 사다리 설치
    if (check_ladder()) { // 현재 통과하는 경우라면 
        ladder[y][x] = 0; //백트레킹을 위한 초기화
        return cnt;
    }    
    if (cnt == 3) { // 사다리 3개를 설치했지만, 통과하지 못하는 경우
        ladder[y][x] = 0; // 백트레킹
        return 987654321; // 불가능한 경우
    }    
    // 바로 옆에 설치하면 안된다.
    

    for (int i = y;i <= h;i++) { 
        for (int j = 1;j < n;j++) {      
            ret = min(ret, dfs(i, j, cnt+1)); // 최소 경우의 수를 구한다. 완전 탐색
        }
    }    
    ladder[y][x] = 0; // 사다리 제거
    return ret;
}


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

    cin >> n >> m >> h; // n개의 가로선 m개의 사다리, h개의 새로선
    memset(ladder, 0, sizeof(ladder));
    for (int i = 0;i < m;i++) { // 사다리 설치
        int a, b;
        cin >> a >> b;
        ladder[a][b] = 1;
    }
    int ans = 987654321;
    
    if(check_ladder()) cout << 0; // 추가 안해도 되는 경우
    else { // 사다리를 추가적으로 설치해야하는 경우        
        for (int i = 1;i <= h;i++) { // 완전 탐색
            for (int j = 1;j < n;j++) {
                ans = min(ans, dfs(i, j, 1)); // 최소 경우의 수 구함
            }
        }
        if (ans > 3) cout << -1 << endl; // 설치가 불가능한 경우
        else cout << ans << endl;            
    }
           
    return 0;
}