BOJ 15684 - 사다리 조작(C++)

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

15684번: 사다리 조작

풀이

추가한 가로선이 3개가 초과되지 않도록 모든경우의 수를 확인

원래의 세로선으로 돌아가는 지 세로선마다 확인

왼쪽으로 갈지, 오른쪽으로 갈지 구별하기 위해 왼쪽에서 오른쪽으로 이어지는 시작점만 true로 표기

if (map[y][now])
    now++;
else if (map[y][now - 1])
    now--;

 

ex)

 

#include <iostream>
 
using namespace std;
 
int N, M;
bool map[31][11];
int MIN = 987654321;
bool check() {
    for (int x = 1; x <= M; x++) {//세로선마다 확인
        int now = x;
        for (int y = 1; y <= N; y++) {
            if (map[y][now])//가로선 : 현재 위치에서 시작
                now++;
            else if (map[y][now - 1])//가로선 왼쪽에서 시작
                now--;
        }
        if (now != x)return false;
    }
    return true;
}
 
void setting(int y,int x, int cnt) {
    if (cnt > 3)
        return;
    if (check()) {//세로선 마다 자기 자리를 찾아가면 현재 상황에서 가로선을 더 추가할 필요 X
        if (cnt < MIN)
            MIN = cnt;
        return;
    }
   
    for (int i = y; i <=N; i++,x=1) {
        for (int j = x; j < M; j++) {
            if (map[i][j] || map[i][j - 1] || map[i][j + 1])continue;//가로선이 접하는 경우를 pass
            map[i][j] = true;
            setting(i, j + 2, cnt + 1);//접하는 경우가 없게끔 +2
            map[i][j] = false;
        }
    }
}
 
int main() {
    int C;
    cin >> M >> C >> N;
 
    for (int i = 0; i < C; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1;
    }
    setting(1, 0, 0);
 
    if (MIN > 3)
        cout << -1;
    else
        cout << MIN;
}