[BOJ] 백준 15684 사다리 조작 c++ (구현, 백트래킹)

 

  문제

---

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

 

 

  풀이

---

문제 조건에 사다리를 최대 3개만 설치 가능하다는 것을 보고 바로 백트래킹으로 구현했습니다. 백트래킹의 진행 조건으로 사용한 것은 3개를 초과하는가? 현재 저장된 정보보다 값이 적은가? 조건에 맞도록 구현이 되었는가? 총 3가지입니다. 3개를 초과하는 경우엔 의미가 사라지고, 이미 저장된 답보다 커지면 불필요한 계산, 조건에 맞지 않으면 성립 자체가 되지 않기에 탈출 조건으로 지정해 줬습니다. 

void dfs(int n, int h, int cnt, int y)
{
    if (cnt >= ans)
        return;
    if (check(n, h))
    {
        ans = cnt;
        return;
    }
    if (cnt == 3)
        return;
...

 

사다리가 규칙에 맞게 설치되었는지 확인하는 것은 추가로 check 함수를 구현하여 만들었습니다. 사다리의 각 출발점에서 시작해 왼쪽에 막대기가 있으면 -1, 오른쪽에 막대기가 있으면 +1을 해주는 방식이며, 내려가고 있는 세로 막대기를 기억해 마지막에 출발 지점과 같은지 검사하는 방식으로 구현했습니다. 

bool check(int n, int h)
{
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        for (int j = 1; j <= h; j++)
        {
            if (tmp + 1 <= n && ladder[j][tmp] == 1)
                tmp++;
            else if (tmp - 1 > 0 && ladder[j][tmp - 1] == 1)
                tmp--;
        }

        if (tmp != i)
            return false;
    }
    return true;
}

 

앞선 조건들에서 문제가 없고 더 진행할 수 있는 경우 현재 위치, 좌, 우의 가로 막대 상태를 확인하여 백트래킹을 진행했습니다. 이때 불필요한 중복 검사를 피하기 위해서 y값을 저장해 i가 진행하던 위치부터 이어서 할 수 있도록 만들었습니다. 

for (int i = y; i <= h; i++)
{
    for (int j = 1; j < n; j++)
    {
        if (ladder[i][j] == 0 && ladder[i][j - 1] == 0 && ladder[i][j + 1] == 0)
        {
            ladder[i][j] = 1;
            dfs(n, h, cnt + 1, i);
            ladder[i][j] = 0;
        }
    }
}

 

 

  전체 코드

---

#include <iostream>
using namespace std;

int ladder[31][11];
int ans = 987654321;

bool check(int n, int h)
{
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        for (int j = 1; j <= h; j++)
        {
            if (tmp + 1 <= n && ladder[j][tmp] == 1)
                tmp++;
            else if (tmp - 1 > 0 && ladder[j][tmp - 1] == 1)
                tmp--;
        }

        if (tmp != i)
            return false;
    }
    return true;
}

void dfs(int n, int h, int cnt, int y)
{
    if (cnt >= ans)
        return;
    if (check(n, h))
    {
        ans = cnt;
        return;
    }
    if (cnt == 3)
        return;

    for (int i = y; i <= h; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (ladder[i][j] == 0 && ladder[i][j - 1] == 0 && ladder[i][j + 1] == 0)
            {
                ladder[i][j] = 1;
                dfs(n, h, cnt + 1, i);
                ladder[i][j] = 0;
            }
        }
    }
}

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

    dfs(n, h, 0, 1);

    cout << (ans > 3 ? -1 : ans) << '\n';

    return 0;
}

 

 

  평가

---

여러 조건을 생각하며 풀어야해서 공부하기에 꽤 괜찮은 문제였습니다.