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

이 포스트는 백준 사이트의 사다리 조작 문제 풀이입니다.

문제

해결 과정

이 문제는 주어진 상황에서 N개의 사다리가 시작 번호와 도착 번호가 동일하도록 만들기 위한
최소의 사다리 추가 수를 구하는 문제입니다.
따라서 이 문제에서는 2가지 과정이 필요합니다.

1. 현재 상태에서 N개가 각자 동일한 번호(시작 번호 = 도착 번호)인지 확인 후 추가된 사리 수 갱신
2. 현 위치에 사다리를 추가할 수 있다면, 추가하고 1번을 실행

2번 과정에서 사다리를 추가할 수 있는 조건은 아래와 같습니다.
현 위치에서 연결된 사다리가 없음(i: 현위치, i-1 -> i 혹은 i <- i+1 연결된 사다리)
즉, 사다리가 전혀 없는 위치에서만 사다리를 추가할 수 있습니다.

이 문제를 해결하고자 저는 모든 경우의 수를 확인하고 매번 유효성을 확인 뒤 조건에 맞는 상태만 검사하는
백트래킹 기법을 사용하였습니다.

코드 구현

#include <iostream>
#include <vector>

#define MAX 31

using namespace std;

int N, M, H, answer = 2e9;
vector<vector<bool>> visited;

void input();
void select_line(int curr_line_num, int ladder_cnt);
bool success_ladder_game();

int main() {
    input();

    select_line(1, 0);
    answer = (answer > 3 ? -1 : answer);
    cout << answer;

    return 0;
}

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> H;
    visited.assign(H + 1, vector<bool>(N + 1, false));
    for(int i = 0; i < M; ++i) {
        int depth, line_number;
        cin >> depth >> line_number;
        visited[depth][line_number] = true;
    }
}

void select_line(int curr_line_num, int ladder_cnt) {
    if(ladder_cnt > 3) {
        return;
    } else if(success_ladder_game()) {
        answer = min(answer, ladder_cnt);
        return;
    }

    for(int line_num = curr_line_num; line_num < N; ++line_num) {
        for(int depth = 1; depth <= H; ++depth) {
            if(visited[depth][line_num]
            || visited[depth][line_num + 1]
            || visited[depth][line_num - 1]) continue;

            visited[depth][line_num] = true;
            select_line(line_num, ladder_cnt + 1);
            visited[depth][line_num] = false;
        }
    }
}

bool success_ladder_game() {
    for(int line_num = 1; line_num <= N; ++line_num) {
        int start_line_num = line_num;
        for(int depth = 1; depth <= H; ++depth) {
            if(visited[depth][start_line_num]) 
                start_line_num += 1;
            else if(visited[depth][start_line_num - 1])
                start_line_num -= 1;
        }

        if(line_num != start_line_num)
            return false;
    }
    return true;
}

실행 결과