[삼성 기출 문제] 백준15684 사다리 조작

문제 링크

어떻게 풀까?

이 문제는 사다리위에 다리가 있다는 것을 어떻게 표시할지를 생각해야합니다.

그리고, 최대 3개의 놓을 수 있는 사다리를 어디에 놓을지, 사다리를 놓은 다음에 해당 사다리 정보가 문제의 조건에 맞는지를 생각해보아야 합니다.

그리고 사다리의 가로줄을 만나면 어떻게 처리할지도 생각해야 하죠!

문제의 조건에 맞는 사다리란, 사다리가 1,2,3,4,5, ... N으로 출발해서, 도착 했을때에도 1,2,3,4,5, ... N 이어야 하죠!

그럼 우선, 사다리에 대한 정보를 어떻게 표시할지에 대해서 생각해봅시다.

사다리입니다!

가로줄과 세로줄이있죠.

그림을 보면, 세로줄과 가로줄을 행과 열에 따라서 2차원 배열로 나타내면 아주 좋을 것이라는 것을 깨달을 수 있습니다!

높이 x의 y번쨰 설치된 가로줄을 (x,y)로 나타냅시다!

참고로 그림을 보면, 세로줄이 5개일 경우, 같은 높이에 설치할 수 있는 가로줄은 최대 4개라는 것을 알 수 있죠!

다음은 사다리를 놓을 수 있는지 판별하는 방법입니다.

문제에서는 가로줄이 연속되거나 접하면 안된다고 나와있기 때문에 이를 쉽게 처리할 수 있습니다.

즉, 위 그림에서 (3,2)에 연결된 사다리를 보면,

(1,3)과 (3,3)의 자리에는 사다리를 연결할 수 없다는 것이죠!

(x,y)에 사다리를 놓을 수 있는지 검사하는 방법은

(x,y-1), (x,y), (x,y+1) 모두 사다리가 놓여있지 않아야 한다는 것 입니다!

 + 1번 세로줄과 4번 세로줄에 놓을 수 있는지에 대한 검사를 쉽게 하기 위해서 가상의 0번 세로줄과 5번 세로줄을 만들어서 가로줄이 연결되어있지 않다고 만들면 편합니다!

위 그림과 같이 (6,1)에 설치가 가능한지 보려면 (6,0)을 봐야하는데, 미리 이 곳에 사다리가 설치되어있지 않다고 표시해놓으면 (6,1)과 (6,2)의 사다리도 없을 때 자동으로 설치 가능한 사다리라고 표시할 수 있습니다.

그럼 이제 사다리를 설치할 수 있는 자리들을 정의할 수 있습니다!

결국 문제에서 사다리를 설치할 수 있는 위치들의 수 i를 저장해 놓으면, 의 시간복잡도로 사다리를 설치해 볼 수 있습니다.

이를 위해서 미리 설치할 수 있는 사다리들에 대한 정보들을 전처리해서 이를 배열 하나에 저장합시다!

typedef struct Cod { int r, c; } cod;
    cod canBuild[300];
 
    int liftCnt;
    bool lift[31][11];
    int n, m, h;
 
    void init()
    {
        scanf("%d %d %d\n", &n, &m, &h);
        liftCnt = 0;
        memset(lift, false, sizeof(lift));
        int in1, in2;
        while (m--)
        {
            scanf("%d %d\n", &in1, &in2);
            lift[in1][in2] = true;
        }
 
        for (int r = 1; r <= h; r++)
        {
            for (int c = 1; c < n; c++)
            {
                if (!lift[r][c - 1] && !lift[r][c] && !lift[r][c + 1])
                {
                    canBuild[liftCnt].r = r;
                    canBuild[liftCnt++].c = c;
                }
            }
        }
    }

이제 사다리를 설치할 수 있는 위치들을 모두 보면서 재귀 함수를 통해 의 함수를 만듭시다.

재귀 함수를 통해 조합을 만들기 어려우신 분은 여기를 참고해주세요!

    int change(int index, int cnt, int changed)
    {
        int res = -1;
 
        if (cnt == changed)
        {
            if (ok() /*is valid*/)
            {
                return cnt;
            }
            else return - 1;
        }
 
        if (index == liftCnt) return -1;
 
        int r = canBuild[index].r, c = canBuild[index].c;
 
        if (!lift[r][c - 1] && !lift[r][c] && !lift[r][c + 1])
        {
            lift[r][c] = true;
            res = change(index + 1, cnt, changed + 1);
            lift[r][c] = false;
        }
 
        if (res != -1) return res;
 
        res = change(index + 1, cnt, changed);
 
        return res;
    }

그럼 이제 마지막 단계입니다.

위 함수의 ok() 함수이죠!

사다리를 다 설치했으면 그 사다리가 그대로 1~n의 순서대로 나오는지 확인하는 것입니다.

다시 사다리 그림을 봅시다.

여기서 (1,1)의 사다리를 주목해보세요!

(1,1)에 사다리가 있기 때문에 1과 2가 순서가 바뀝니다.

(2,3) 사다리는 3과 4가 바뀌겠죠.

즉, (x,y) 사다리에 오면, x번째와 x+1번째 수가 바뀝니다!

일차원 배열로 i번째 세로 사다리에 현재 있는 수를 저장하고, 

높이마다 (x,y) 사다리가 설치되어있는지 확인하고, 설치되어 있다면 x와 x+1번째 수를 바꾸면 됩니다.

그리고, 마지막에 나온 결과 배열이 1~n의 값 그대로 있는지 확인하면 됩니다!

bool ok()
    {
        int num[11];
 
        for (int i = 1; i <= n; i++)
        {
            num[i] = i;
        }
 
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (lift[i][j])
                {
                    swap(num[j], num[j + 1]);
                }
            }
        }
 
        for (int i = 1; i <= n; i++)
        {
            if (num[i] != i) return false;
        }
 
        return true;
    }

코드

#pragma once
#include<iostream>
#include<cstring>
 
using namespace std;
 
struct Lifting_Info
{
    typedef struct Cod { int r, c; } cod;
    cod canBuild[300];
 
    int liftCnt;
    bool lift[31][11];
    int n, m, h;
 
    void swap(int &a1, int &a2)
    {
        int temp = a1;
        a1 = a2;
        a2 = temp;
        return;
    }
 
    void init()
    {
        scanf("%d %d %d\n", &n, &m, &h);
        liftCnt = 0;
        memset(lift, false, sizeof(lift));
        int in1, in2;
        while (m--)
        {
            scanf("%d %d\n", &in1, &in2);
            lift[in1][in2] = true;
        }
 
        for (int r = 1; r <= h; r++)
        {
            for (int c = 1; c < n; c++)
            {
                if (!lift[r][c - 1] && !lift[r][c] && !lift[r][c + 1])
                {
                    canBuild[liftCnt].r = r;
                    canBuild[liftCnt++].c = c;
                }
            }
        }
    }
 
    int max(int i1, int i2)
    {
        return i1 > i2 ? i1 : i2;
    }
 
    int change(int index, int cnt, int changed)
    {
        int res = -1;
 
        if (cnt == changed)
        {
            if (ok())
            {
                return cnt;
            }
            else return - 1;
        }
 
        if (index == liftCnt) return -1;
 
        int r = canBuild[index].r, c = canBuild[index].c;
 
        if (!lift[r][c - 1] && !lift[r][c] && !lift[r][c + 1])
        {
            lift[r][c] = true;
            res = change(index + 1, cnt, changed + 1);
            lift[r][c] = false;
        }
 
        if (res != -1) return res;
 
        res = change(index + 1, cnt, changed);
 
        return res;
    }
 
    bool ok()
    {
        int num[11];
 
        for (int i = 1; i <= n; i++)
        {
            num[i] = i;
        }
 
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (lift[i][j])
                {
                    swap(num[j], num[j + 1]);
                }
            }
        }
 
        for (int i = 1; i <= n; i++)
        {
            if (num[i] != i) return false;
        }
 
        return true;
    }
}lifintInfo;
 
 
int main()
{
    lifintInfo.init();
 
    int max = lifintInfo.liftCnt > 3 ? 3 : lifintInfo.liftCnt;
 
    for (int i = 0; i <= max; i++)
    {
        int res = lifintInfo.change(0, i, 0);
        if (res != -1)
        {
            printf("%d\n", res);
            return 0;
        }
    }
    printf("%d\n", -1);
    return 0;
}

시간 복잡도

최대 설치할 수 있는 사다리 수는 n*h개 입니다!

즉, 입니다.