15684 사다리 조작

15684 사다리 조작

백트래킹을 이용해 완전탐색하되 조건을 주어 가지치기 하면서 풀었다.

1. 코드를 간결하게 만들기 위해 사다리를 놓을 수 있는 좌표를 벡터에 모두 넣는다.

2. 연속되지 않도록 사다리를 놓으면서 (dfs함수에서 map[v[idx].first][v[idx].second] = 1) 사다리 조작이 가능한지 확인한다.

3. 조작이 가능하다면 res를 최신화 시켜준다.

4. 백트래킹 시에 카운트값이 3보다 크거나 res값과 같거나 크면 함수를 종료한다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#define P pair<int, int>
#define INF 987654321
using namespace std;
 
int n, m, h, res;
int map[33][13];
vector<P> v;
 
int downLadder(int x) {
    int i = 1;
    int cur = x;
    while (i <= h) {
        if (cur > 1 && map[i][cur - 1] == 1) {
            cur--;
        }
        else if(cur < n){
            if (map[i][cur] == 1) {
                cur++;
            }
        }
        i++;
    }
    return cur;
}
 
bool isOK() {
    for (int i = 1; i <= n; i++) {
        if (i != downLadder(i)) return false;
    }
    return true;
}
 
void dfs(int idx, int cnt) {
    if (cnt > 3 || cnt >= res) {
        return;
    }
 
    map[v[idx].first][v[idx].second] = 1;
 
    if (isOK()) {
        res = min(res, cnt);
    }
    else {
        for (int i = idx + 1; i < v.size(); i++) {
            if (map[v[i].first][v[i].second - 1] == 1 || map[v[i].first][v[i].second + 1] == 1) continue;
            dfs(i, cnt + 1);
        }
    }
 
    map[v[idx].first][v[idx].second] = 0;
}
 
int main() {
    scanf("%d %d %d", &n, &m, &h);
 
    //가로선 추가
    int x, y;
    while (m--) {
        scanf("%d %d", &x, &y);
        map[x][y] = 1;
    }
 
    //가로선 놓을 수 있는 공간 벡터에 추가
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j < n; j++) {
            if (map[i][j] == 0) {
                v.push_back(P(i, j));
            }
        }
    }
 
    //백트래킹
    if (isOK()) {
        printf("0\n");
    }
    else {
        res = INF;
        for (int i = 0; i < v.size(); i++) {
            if (map[v[i].first][v[i].second - 1] == 1 || map[v[i].first][v[i].second + 1] == 1) continue;
            dfs(i, 1);
        }
 
        if (res == INF) printf("%d\n", -1);
        else printf("%d\n", res);
    }
 
 
    
}