[15684번] 사다리 조작

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.

위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.

사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.

위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.

1번 세로선	2번 세로선

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

문제접근법.

1. 백트래킹으로 사다리의 조합을 확인해야 한다. 3개가 되는 순간에 백트래킹 함수는 더 이상 들어가지 않는다.

2. 1부터 N까지 H단계까지 내려오며 확인해봐야 한다.

 

 이 문제는 정답률에 비해서 어렵지 않다. 단 주의해야 할 점은, 백트래킹 함수에서 범위에 따라서 시간초과가 발생한다. 범위를 생각해서 잘 잡아주어야 한다.

 

 또한, 사다리 타기 할 때, 두 선이 연속하지 않는 점을 기억해야 한다. 이 문제는 백트래킹을 최소화하는 것이 핵심이다. 백트래킹이 이해되지 않는다면, 백트래킹 관련 기본 예제들을 이해하는 것을 추천한다.

 

 문제에 주어진 조건에 의하면, a, b는 가로선 a는 세로선 b에 대하여 b+1까지 이어져있다는 것을 확실하게 인지하고 문제를 풀어야 한다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int N, M, H;
int a, b;
int arr[31][11] = { 0 };
int answer = 4;
 
void check(int end) {
    int i_cnt = 0;
    // Check Answer
    for (int i = 1; i <= N; i++) {
        int temp = i;
        for (int j = 1; j <= H; j++) {
            // MOVE RIGHT
            if (temp + 1 <= N) {
                if (arr[j][temp] == 1) {
                    temp += 1;
                    continue;
                }
            }
 
            // MOVE LEFT
            if (temp - 1 >= 1) {
                if (arr[j][temp - 1] == 1) {
                    temp -= 1;
                    continue;
                }
            }
        }
        if (temp != i)
            break;
        i_cnt++;
    }
 
    // FInsih
    if (i_cnt == N) {
        answer = min(answer, end);
    }
}
 
void dfs(int r, int c, int cnt) {
    if (cnt == 3) {
        return;
    }
 
    for (int i = r; i <= H; i++) {
        for (int j = 1; j < N; j++) {
            if (arr[i][j] == 0) {
                if (j - 1 >= 1 && arr[i][j - 1] == 1)
                    continue;
 
                if (j + 1 < N && arr[i][j + 1] == 1)
                    continue;
 
                arr[i][j] = 1;
                check(cnt + 1);
                dfs(i, j, cnt + 1);
                arr[i][j] = 0;
            }
        }
    }
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    memset(arr, 0, sizeof(arr));
 
    cin >> N >> M >> H;
    for (int i = 1; i <= M; i++) {
        cin >> a >> b;
        arr[a][b] = 1;
    }
 
    //Backtracking
    check(0);
    if (answer == 4)
        dfs(1, 1, 0);
    if (answer == 4)
        answer = -1;
 
    cout << answer << endl;
    return 0;
}