[백준 15684] 사다리 조작, C++

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

15684번: 사다리 조작

 본 문제는 삼성 SW 역량 테스트 기출 문제다. 문제를 간단히 설명하면 사다리 타기 게임에서 가로선을 3개 이하로 추가하여 1은 1로 2는 2로 3은 3으로 결과가 나오도록 조작하는 문제다. 문제에서 가로선의 최대 개수가 270개다. 270^3은 19,683,000‬로 1억보다 작기 때문에 브루트 포스로 문제를 해결할 수 있다. 사다리 게임을 구현하기 위해 2차원 배열을 이용하였다. 사다리 게임은 왼쪽 → 오른쪽 사다리로 가는 경우와 오른쪽 → 왼쪽 사다리로 가는 경우 2가지가 존재한다. 따라서, 왼쪽 → 오른쪽 사다리인 경우를 1, 오른쪽 → 왼쪽 사다리로 가는 경우를2로 저장하였다.

사다리 조작 문제에서 주의해야할 사항은 추가하는 가로선을 최소로 하는 경우다. 코드를 보면 3중 for문으로 작성하였기 때문에 3개를 추가했을 경우부터 탐색한다. 그러나 1개를 추가했을 때, 답이 되는 TC가 존재하므로 답에 맞는 조건이 발생했다고 반복문을 종료하면 안된다.

#include <cstdio>
#include <vector>
 
using namespace std;
 
int d[31][11] = {0};
int n, m, h;
int ans = -1;
 
vector<pair<int, int>> a;
 
bool chk() {
    for (int j = 1; j <= n; j++) {
        int now = j;
        for (int i = 1; i <= h; i++) {
            if (d[i][now] == 1) now += 1;
            else if (d[i][now] == -1) now -= 1;
        }
        if (now != j) return false;
    }
    return true;
}
 
void cal() {
    if (chk()) {
        ans = 0;
        return;
    }
    for (int i = 0; i < a.size(); i++) {
        int ix = a[i].first;
        int iy = a[i].second;
        if (d[ix][iy] == 0 && d[ix][iy+1] == 0) {
            d[ix][iy] = 1;
            d[ix][iy+1] = -1;             
            if (chk()) {
                if (ans == -1 || ans > 1) ans = 1;
            }
            for (int j = i+1; j < a.size(); j++) {
                int jx = a[j].first;
                int jy = a[j].second;
                if (d[jx][jy] == 0 && d[jx][jy+1] == 0) {
                    d[jx][jy] = 1;
                    d[jx][jy+1] = -1;
                    if (chk()) {
                        if (ans == -1 || ans > 2) ans = 2;
                    }
                    for (int k = j+1; k < a.size(); k++) {
                        int kx = a[k].first;
                        int ky = a[k].second;
                        if (d[kx][ky] == 0 && d[kx][ky+1] == 0) {
                            d[kx][ky] = 1;
                            d[kx][ky+1] = -1;
                            if (chk()) {
                                if (ans == -1 || ans > 3) ans = 3;
                            }
                            d[kx][ky] = 0;
                            d[kx][ky+1] = 0;
                        }
                    }
                    d[jx][jy] = 0;
                    d[jx][jy+1] = 0;
                }
            }
            d[ix][iy] = 0;
            d[ix][iy+1] = 0;
        }
    }
    return;
}
 
int main() {
    scanf("%d %d %d", &n, &m, &h);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        d[x][y] = 1;
        d[x][y+1] = -1;
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == 0) a.push_back(make_pair(i, j));
        }
    }
    cal();
    printf("%d\n", ans);
}