[BOJ 15684] 사다리 조작(C++)

사다리 조작(Gold 4)

문제

전체 문제 보기

15684번: 사다리 조작

접근법

이번 문제는 사다리를 놓을 수 있는 모든 경우의 수를 백트레킹으로 완전탐색해서 풀 수 있는 문제입니다. 문제에서는 최대 추가할 수 있는 사다리 개수를 3개로 제한하였습니다. 우리가 찾아야 할 값은 추가 사다리의 최소 개수이기 때문에 추가 사다리 개수가 0, 1, 2, 3인 경우를 각각 탐색하여 이전 탐색에서 해답을 찾은 경우 더 이상 탐색을 하지 않는 방식으로 최적화할 수 있습니다.

 

각 탐색에서는 목표 탐색 깊이에 도착할 경우 Check 함수를 활용하여 같은 i번째에서 출발해서 i번째에 도착하는지 확인할 수 있습니다. 탐색에 성공할 경우 깊이값을 반환하여 백트레킹을 종료시키고, 탐색에 실패할 경우 -1을 반환하여 계속 탐색을 이어나갑니다.

 

새로운 가로선을 추가하기 위해서는 r이 행, c가 열일때 (r, c-1) / (r, c) / (r, c+1)에 모두 가로선이 없어야 합니다. 따라서 백트레킹으로 가로선을 추가할 때 다음과 같은 조건을 만족할 경우에만 가로선을 추가합니다.

if (ladder[r][c] == 0 && ladder[r][c-1] == 0 && ladder[r][c+1] == 0)
{
    // 가로선 추가 후 추가 탐색
}

아래는 전체 소스코드입니다.
(체점결과 메모리 2024 KB / 시간 462ms으로 나옵니다. 많은 풀이가 0~4ms로 문제를 해결하고 있는 것으로 보아 더 최적화할 수 있을것으로 판단됩니다. 이후 최적화를 진행하여 다시 수정할 계획입니다.)

전체 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

const int INF = 1'000;
int N, M, H; // (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)
vector<vector<int>> ladder;

int GetEnd(int c)
{
    for (int i = 1; i < H + 1; ++i)
    {
        if (ladder[i][c] == 1)
            c++;
        else if (ladder[i][c - 1] == 1)
            c--;
    }
    return c;
}
bool Check()
{
    for (int i = 1; i < N + 1; ++i)
    {
        if (i != GetEnd(i)) return false;
    }
    return true;
}
int BT(int dep, int idx, int targetDep)
{

    if (dep == targetDep)
    {
        if (Check()) return dep;
        else return -1;
    }

    for (int i = 0; i < idx; ++i)
    {
        const int r = i / (N - 1) + 1;
        const int c = i % (N - 1) + 1;

        // 가로선을 오른쪽으로 연결 후 백트레킹 탐색
        // c가 N보다 작고, c-1, c, c+1세로 r높이에 다른 가로선이 없는 경우 
        if (ladder[r][c] == 0 && ladder[r][c-1] == 0 && ladder[r][c+1] == 0)
        {
            // 연결
            ladder[r][c] = 1;

            // 탐색
            int retval = BT(dep + 1, i, targetDep);
            if (retval != -1) return retval; // 탐색 성공

            // 연결 해제
            ladder[r][c] = 0;
        }
    }
    return -1;
}

int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    cin >> N >> M >> H;
    ladder.resize(H + 1);
    for_each(ladder.begin(), ladder.end(), [](vector<int>& row) {
        row.resize(N + 2, 0); });

    while (M--)
    {
        int a, b; // a: r , b: c
        cin >> a >> b;
        ladder[a][b] = 1;
    }
    const int maxIdx = (N - 1) * H;

    int answer{ };
    for (int i = 0; i <= 3; ++i)
    {
        answer = BT(0, maxIdx, i);
        if (answer != -1) break;
    }

    cout << answer << endl;
    return 0;
}