[백준 15684] 사다리 조작 C++

15684번: 사다리 조작

완전 탐색, 백트래킹

삼성 SW 기출

---

1. 문제 해결 아이디어

 

처음에 문제에 대한 감이 안 왔다.

백트래킹이라기엔 H가 너무 커 보였고 그래프라 하기엔 간선 정보를 어떻게 담아야 할지 생각이 안 났다.

그러다 완전 탐색 문제라는 말을 듣고 힘들게 접근을 시도할 수 있었다.

 

지금까지 만든 사다리에서 사다리 타기를 했을 때 각 line의 도착점이 시작 line의 번호와 같아야 true를 return 하는 함수를 만들었다.

그리고 사다리를 놓지 못하는 조건을 걸어주고, 놓을 수 있다면 사다리를 놓고 현재 함수를 재귀 호출하는 일반적인 백트래킹 dfs를 사용했다.

처음에 당연히 시간 초과가 날 줄 알았고, 시간초과가 났다.

 

시간을 줄일 로직이 떠오르지 않아서 결국 다른 분의 코드를 참고했다.

그런데 다들 나랑 코드의 흐름이 비슷했다.

차이점이라곤 나는 Recursion함수에서 더 이상 가로선을 놓을 수 없으면 사다리 결과를 반환하는 함수를 매번 호출하게 되는 반면, 다른 분들은 함수를 따로 호출하지 않고 Recursion함수 내부에서 사다리 결과를 바로 알 수 있는 코드를 작성하셨다는 점이다.

그래서 설마설마하는 마음으로 함수 호출 부분(Riding())을 Recursion함수 내부로 옮겼더니 맞았습니다!! 가 떴다

황당하지만 그만큼 Riding() 함수가 많이 호출되었다는 뜻이고 그만큼 호출에 따른 오버헤드가 크다고 이해했다.

실제로 호출에 따른 오버헤드 때문에 시간 초과가 걸린 적은 이번이 처음이었다.

 

 

사다리 타기를 코드로 구현해볼 수 있게 해 준 좋은 문제였다!

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, H, Now;
int ladder[31][11];
bool is_find;
 
void input(){
    int a, b;
    cin >> N >> M >> H;
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        ladder[a][b] = 1;
    }
}
 
bool Riding(){
    for(int i = 1; i <= N; i++){
        int line = i;
        for(int height = 1; height <= H; height++){
            if(ladder[height][line]) line += 1;
            else if(ladder[height][line-1]) line -= 1;
        }
        if(line != i) return false;
    }
    
    return true;
}
 
void Recursion(int nowheight, int horizoncnt){
    if(horizoncnt == 0){
        bool tmp = true;
        // **문제의 부분**
        for(int i = 1; i <= N; i++){
            int line = i;
            for(int height = 1; height <= H; height++){
                if(ladder[height][line]) line += 1;
                else if(ladder[height][line-1]) line -= 1;
            }
            if(line != i) return;
        }
        if(tmp){
            cout << Now;
            exit(0);
        }
    }
    
    for(int i = nowheight; i <= H; i++){
        for(int r = 1; r < N; r++){
            if(ladder[i][r-1] || ladder[i][r+1] || ladder[i][r]) continue;
            
            ladder[i][r] = 1;
            Recursion(i, horizoncnt-1);
            ladder[i][r] = 0;
        }
    }
}
 
 
void solve(){
    int horizon = 0;
    while(horizon <= 3){
        Now = horizon;
        Recursion(1, horizon);
        horizon++;
    }
    
    cout << -1;
}
 
int main(){
    fasti
    input();
    solve();
    
    return 0;
}