[C++] 백준(BOJ) - 15684 : 사다리 조작

02 Nov 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 15684 : 사다리 조작(링크)

알고리즘

1. 브루트포스
2. 백트래킹

풀이

1. 백트래킹
   • 방문하지 않아도 될 경우의 수는 생각하지 않는다

     재귀함수 cnt >= res인 경우 진행할 필요가 없다

2. 이차원 배열을 통해 사다리의 위치를 설정한다
3. 일반적인 y축 기반 탐색 외에 x축 기반 탐색이 필요한 경우에는 적극 활용하도록 한다

코드

// BOJ-15684 : 사다리 조작
#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, m, h, visited[34][34], res = INF;

bool check()
{
    for (int i = 1; i <= n; i++)
    {
        int start = i;
        for (int j = 1; j <= h; j++)
        {
            if (visited[j][start]) start++;
            else if (visited[j][start - 1]) start--;
        }
        if (start != i) return false;
    }
    return true;
}

void go(int here, int cnt)
{
    if (cnt > 3 || cnt >= res) return; // 현재 탐색 진행할 부분의 cnt가 res보다 더 커지면 진행할 필요가 없다 // 백트래킹 
    if (check()) // 사다리 조작에 성공했는지 확인
    {
        res = min(res, cnt);
        return;
    }
    // 조작 사다리 백트래킹으로 세우기
    // 300C3 약 450만 경우의 수 = 백트래킹으로 풀이 가능
    for (int i = here; i <= h; i++) // 가로 방향 기준으로 확인
    {
        for (int j = 1; j <= n; j++)
        {
            if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue; // 사다리는 연속해서 놓을 수 없다
            visited[i][j] = 1;
            go(i, cnt + 1);
            visited[i][j] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> h;

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        visited[a][b] = 1;
    }

    go(1, 0); // 1번 사다리 부터 시작, 사다리 개수 0개로 시작, 백트래킹

    cout << res << '\n';

    return 0;
}

평가

• 완전탐색이나 백트래킹의 경우 우선 대략적인 시간복잡도를 계산해보고 가능할 것 같으면 단계적으로 알고리즘을 구현해 나간다
• y축 기반의 전체 탐색에 얽매여 있지 않기
• 이차원 배열과 idx 값을 활용하여 boolean형 함수 만들기
• 백트래킹의 기본 형
  • 기저사례
  • 방문처리 check
  • 재귀
  • 방문처리 uncheck