백준 15684번 사다리 조작

🔒[문제 url]

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

🔑알고리즘

• 사다리를 0개 설치한 모든 경우의 수
• 사다리를 1개 설치한 모든 경우의 수
• 사다리를 2개 설치한 모든 경우의 수
• 사다리를 3개 설치한 모든 경우의 수
  를 차례대로 살펴보고, 문제의 요구대로 조작될 수 없다면 -1을 출력하는 문제이다.
  
  ladder[i][j]에 가로선을 놓기 위해선 다음을 만족해야 한다.

!ladder[i][j - 1] && !ladder[i][j] && !ladder[i][j+1]

BruteForce + BackTracking으로 $k \le 3$개의 사다리를 놓은 경우 중 문제의 요구대로 조작되었다면, $k$가 출력 답안이 된다.

🐾부분 코드

bool n_to_n()
{
    for(int i = 1; i <= n; i++)
    {
        int x = 1, y = i;
        while(x <= h)
        {
            // 연결된 가로선이 있다면 이동
            if(ladder[x][y] == 1) y++;
            else if(ladder[x][y - 1] == 1) y--;

            // 아래로 이동
            x++;
        }
        //cout << i << " to " << y << '\n';
        if(i != y) return false;
    }
    return true;
}

<사다리 조작 확인 함수>
문제의 요구대로 사다리가 조작되었는지 확인한다.
즉, $1\le i \le n$의 내의 모든 수가 $i$번에서 출발하여 $i$번으로 도착하면 true를 반환한다.

bool DFS(int cnt, int limit)
{

    if(cnt == limit)
    {
        if(n_to_n()) return true;
        else return false;
    }

    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= h; j++)
        {
            // 사다리를 설치할 수 없으면 continue
            if(ladder[j][i] || ladder[j][i - 1] || ladder[j][i + 1])
                continue;


            ladder[j][i] = 1;
            if(DFS(cnt + 1, limit)) return true;
            // BackTracking
            ladder[j][i] = 0;

            // 시간 단축 핵심 : 설치할 수 있는 곳까지 이동
            while(!ladder[j][i-1] && !ladder[j][i+1]) j++;
        }
    }
    return false;
}

<사다리 설치 함수>
limit을 0 ~ 3으로 늘려가며, limit만큼 사다리를 설치한다.
설치를 완료하면 n_to_n() 함수를 호출해 조작을 확인한다.
재귀적으로 호출하는 DFS() 앞뒤로 ladder의 상태가 다를 수 있으므로, while(!ladder[j][i-1] && !ladder[j][i+1]) j++;
위 코드를 통해 가로선를 설치할 수 있는 구간을 찾는 것이 시간단축의 핵심이다.

void SOLVE()
{

    int ans = 0;
    while(ans <= 3)
    {
        if(DFS(0, ans)) break;
        ans++;
    }
    if(ans <= 3) cout << ans;
    else cout << -1;
}

<BruteForce 반복>
설치할 가로선의 갯수인 ans를 $0$부터 $3$까지 늘려가며 조작을 확인한다.

🪄전체 코드

#include <iostream>
using namespace std;

int n,m,h;
int ladder[31][11];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> h;
    for(int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b;
        ladder[a][b] = 1;
    }
}

bool n_to_n()
{
    for(int i = 1; i <= n; i++)
    {
        int x = 1, y = i;
        while(x <= h)
        {
            // 연결된 가로선이 있다면 이동
            if(ladder[x][y] == 1) y++;
            else if(ladder[x][y - 1] == 1) y--;

            // 아래로 이동
            x++;
        }
        //cout << i << " to " << y << '\n';
        if(i != y) return false;
    }
    return true;
}



bool DFS(int cnt, int limit)
{

    if(cnt == limit)
    {
        if(n_to_n()) return true;
        else return false;
    }

    for(int i = 1; i < n; i++)
    {
        for(int j = 1; j <= h; j++)
        {
            // 사다리를 설치할 수 없으면 continue
            if(ladder[j][i] || ladder[j][i - 1] || ladder[j][i + 1])
                continue;


            ladder[j][i] = 1;
            if(DFS(cnt + 1, limit)) return true;
            // BackTracking
            ladder[j][i] = 0;

            // 시간 단축 핵심 : 설치할 수 있는 곳까지 이동
            while(!ladder[j][i-1] && !ladder[j][i+1]) j++;
        }
    }
    return false;
}

void SOLVE()
{

    int ans = 0;
    while(ans <= 3)
    {
        if(DFS(0, ans)) break;
        ans++;
    }
    if(ans <= 3) cout << ans;
    else cout << -1;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

후기..? 사진으로 요약한다...