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

개인적으로 '감시' 문제보다 구현할게 많지 않아서 간단하게 풀수 있는 문제입니다.  

먼저 '연구소'라는 문제를 풀어본사람은 비슷하다는 느낌을 많이 받았을 것입니다.  

먼저 사다리의 시작점-도착점이 일치하는지 여부를 판별하기전에 사다리부터 놓아야합니다.  

문제 해결 절차 

1. 사다리를 h*n인덱스를 탐색하며 양사이드 [h][n-1]과 [h][n+1], [h][n]이 비어있는 사다리인지 확인 
   해본다. (h가 세로선이므로 행 n이 가로선 번호이므로 열이다.헷갈리지 않게 주의하자) 
2. 비어있다면 사다리를 놓고 재귀호출~ 그리고 재귀호출 끝나고 돌아오면 백트래킹으로 다시 사다리를 
    없애주도록 하자. 생각보다 복잡도가 심하지 않은 편이다. (양사이드와 현재 인덱스가 있으므로 )
 시간을 최대한 줄이자
- 가지치기를 잘하여 사다리들이 시작점으로 모두 도착하는경우 더이상 탐색하지 않는다. 
- 탐색과정에서 행단위로 양사이드 및 해당 열에 사다리를 모두 놓았다면, 해당 행 이상인 부분만 탐색. 

위 조건만 잘 만족시켜준다면 시간안에는 통과할수 있을 것이다. 

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

<Code>

// Minerba
#include<iostream>
using namespace std;
bool a[31][11]; int n, m, h, Ladder;    bool res;
bool Count_Ladder() {
    for (int i = 1; i <= n; i++) { // 세로선 번호  // i는 반복문 시작전 최초의 시작점, pt는 변경될 시작점
        int pt = i;
        for (int j = 1; j <= h; j++) {
            if (a[j][pt]) pt += 1;   // 오른쪽으로 이동
            else if (pt - 1 > 0 && a[j][pt - 1]) pt -= 1; // 왼쪽으로 이동 
        }
        if (i == pt) continue;
        else
            return false;
    }
    res = true; 
    return true;
}
 
void dfs(int x, int cnt) {
    if (res) return;
    if (cnt == Ladder) {
        if (Count_Ladder())  m = cnt;
        return;
    }
    for (int i = x; i <= h; i++) {   // 기존 행에 사다리를 놓았다면 해당 행과 같거나 더 커야한다.
                                     // 사다리가 역주행해서 위로 올라갈순 없으니...
        for (int j = 1; j < n; j++) {
            if (!a[i][j]) {
                if (!a[i][j - 1] && !a[i][j + 1]) { // 연속되지 않은 가로선 
                    a[i][j] = 1;
                    dfs(i, cnt + 1);
                    a[i][j] = 0;
                }
            }
        }
    }
    return;
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;
    while (m--) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 0; i <= 3; i++) {
        Ladder = i;
        dfs(1, 0);
        if (res) break;
    }
    if (!res) cout << -1 << '\n';
    else cout << m << '\n';
    return 0;
}