백준 15684번: 사다리 조작 (C++)

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

초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.

사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.

그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.

사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.

사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,4)에서 출발하는 사다리를 놓을 수 없기 때문에 이에 맞는 처리를 해주면 된다.

#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
int col, m, row, map[31][11], st = 0;
bool isused[31][11], ansUpdate = false;
vector<pii> v;
int ans = -1;
 
void btk(int k, int num) {
    if (k == num) { //사다리의 개수
        
        bool suc = true; //답을 찾았는지
        for (int i = 1; i <= col; i++) {
            pii pos = { 1, i }; //출발 지점
            bool isFirst = true; //true면 가로로 이동, false면 세로로 이동
            while (pos.first <= row) {
                
                if (map[pos.first][pos.second] != 0) { //가로 사다리 만나면
                    if (isFirst == true) { //가로이동 할 차례
                        pos.second = map[pos.first][pos.second];
                        isFirst = false; //다음엔 세로 이동 하도록
                        
                    }
                    else { //세로로 이동할 차례
                        isFirst = true; //다음엔 가로로 이동하도록
                        pos.first++;
                        
                    }
                }
                else 
                    pos.first++; //가로 사다리가 없는 곳이면 아래로 이동
                
            }
            if (pos.second != i) { //출발점과 도착지점의 열값이 다르면 실패
                suc = false;
                break;
            }
        }
        if (suc) {
            ansUpdate = true;
            ans = num;
        }
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        int r = v[i].first; //r,c와 r,c+1이 사다리
        int c = v[i].second;
        if (!isused[r][c] && !isused[r][c + 1]) {
            isused[r][c] = true;
            isused[r][c + 1] = true;
            st = i;
            map[r][c] = c + 1; //r,c에서 사다리를 보면 r, c+1로 이동
            map[r][c + 1] = c; //위와 반대
            btk(k + 1, num);
            if (ansUpdate) return; //정답 찾으면 백트레킹 그만
            isused[r][c] = false;
            isused[r][c + 1] = false;
            map[r][c] = 0;
            map[r][c + 1] = 0;
        }
    }
}
int main(void) {
    cin >> col >> m >> row;
    for (int i = 0; i < m; i++) {
        int rw, st;
        cin >> rw >> st;
        map[rw][st] = st + 1;
        map[rw][st + 1] = st;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) 
            if (map[i][j] != 0)
                isused[i][j] = true; //처음부터 가로 사다리가 놓여진 곳
    
 
    //가로막대 놓을 수 있는 곳 찾아서 벡터에 시작점만 담기
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col - 1; j++) { //어짜피 가장 끝 열에는 사다리를 둘 수 없으니까 col -1
            if (!isused[i][j] && !isused[i][j + 1]) {
                isused[i][j] = true;
                isused[i][j + 1] = true;
                v.push_back({ i, j });
                isused[i][j] = false;
                isused[i][j + 1] = false;
            }
        }
    }
    
    
    for (int i = 0; i <= 3; i++) {
        if (ansUpdate) break; //최솟값 찾는 거니까 하나라도 찾으면 그만
        btk(0, i);
    }
    printf("%d", ans);
    return 0;
}