[백준 알고리즘] 15684번 사다리 조작

다음 본 문제는 또 삼성 상반기 문제 였던 사다리 조작문제입니다. 15684 사다리 조작

전 이 문제 손도 못 댔었는데.. 그 이유가 방법을 모른다는 것이긴 하지만..! 감이 완전 안오던 문제였어요. 이제 와서 풀어보고 느낀 것이지만, 정말 기초적인 개념이 매우 중요한 문제 였던 것 같습니다.

이번 문제는 전에 풀었던 감시문제와 비슷하게 순열 조합 개념이 들어갑니다. 정말 당황 스럽게도… 답은 전수 조사 였습니다.

삼성은 약간 DFS, BFS랑 조합을 섞은 시뮬레이션같은 문제를 좋아하나 봅니다.ㅋㅋㅋ

vector<int> T;
int arr[4] = {1,2,3,4};
vector<vector<int>> com;
void swap(int *a, int *b ){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void combination(int n, int r){
    if(r == 0){
        com.push_back(T);
        return;
    }else if(n<r){
        return;
    }
    else {  //loop이 아님
        T.push_back(arr[n-1]);
        combination(n-1, r-1);  //n-1Cr-1: 현재 아이템을 선택한 경우
        T.pop_back();
        combination(n-1, r);    //n-1Cr: 현재 아이템을 선택하지 않은 경우
    }
}

먼저 조합코드를 살펴봅시다. 주석에도 써놨지만 이렇게 됩니다.

---

• n에 대해 숫자를 선택
• 해당 숫자를 조합 세트에 집어넣고 다른 숫자를 선택하기 위해 재귀 호출(combination(n-1,r-1))
• 해당 숫자를 선택하지 않으므로 조합 세트에서 뺀 후에 재귀 호출(combination(n-1,r))

---

이를 활용하면 문제를 바로 해결할 수 있습니다. 왜 일까요?

결국 사다리 맵을 순방 하면서 빈 공간에 하나하나 놓아 가면서 체크하면 된다는 것이죠. 코드가 매우 짧으니까 한번 봅시다.

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int N,M,H;
int map[31][35]={0,};
int ans=-1;
bool check()
{
    for(int start=1; start<=N; start++)
    {
        int end = start;
        for(int x=1; x<=H; x++)
        {
            if(map[x][end]==1) end+=1;
            else if((end-1)>=1 && map[x][end-1]==1) end-=1;
        }
        if(end!=start) return false;
    }
    return true;
}

먼저 check 함수 부터 보면 그냥 1,2,3,4,5가 들어갔다 나와서 1,2,3,4,5인지 체크하는 함수입니다. 간단하네요!

void Find(int x, int r, int q)
{
    if(ans!=-1) return;
    if(r==0)
    {
        if(check()) ans=q;
        return;
    }
    
    for(int i=x; i<=H; i++)
    {
        for(int j=1; j<=N-1; j++)
        {
            if(map[i][j]==0)
            {
                if((map[i][j-1]==0)&&(map[i][j+1]==0))
                {
                    map[i][j]=1;
                    Find(i,r-1,q);
                    map[i][j]=0;
                }
            }
        }
    }
}

다음은 주축이 되는 Find 함수입니다. 아까 위에서 조합 코드랑 비슷하죠? 다른점은 2중 for loop라는거? 코드는 이러합니다.

---

• x는 깊이 수, r은 선택 사다리 개수, q는 선택할 수 있는 사다리 개수
• 맵의 빈 공간을 하나 하나에 사다리를 집어넣으면서 체크하는데 사다리를 다 골랐다면 check 함수를 통해 제대로 되었는지 체크

---

처음엔 첫 줄인 if(ans!=-1) return;를 넣지 않았는데, 저걸 넣은 이유는 답이 구해지면 실행 시간을 단축시키기 위해 중단 시키려고 집어넣었습니다.

int main()
{
    int a,b;
    scanf("%d %d %d",&N,&M,&H);
    for(int i=0; i<M; i++)
    {
        scanf("%d %d",&a,&b);
        map[a][b]=1;
    }
    for(int r=0; r<=3; r++)
    {
        Find(1,r,r);
        if(ans!=-1) break;
    }
    cout<<ans<<endl;
    return 0;
}

다음은 Main 함수입니다. 간단하네요!! 우리는 사다리가 3개 이하일 때만 값을 출력하고, 그 이상은 -1을 출력하니까 사다리 개수가 0,1,2,3일 때 가능한지 체크만 하면 되겠네요!! 진짜 허무하게 간단 했던 풀이네요.. 제가 코딩 하면서 틀렸거나 어려웠던 부분인데 여러분도 자세하게 체크하고자 써보면 이러합니다.

1. 사다리를 안 놓아도 되는 사항 체크 처음엔 사다리가 아예 없는 경우에만 예외 처리를 해서 답을 0으로 출력 시켰는데, 그런 경우엔 사다리가 있지만 놓지 않아도 되는 경우를 체크를 못 하더라구요. 그래서 그냥 0부터 체크하게 설계하였습니다.
2. 시간 단축 체크 위에서도 말했지만, 일말의 수행 경우도 제외시켜서 시간을 단축시켜야 한다는 것!
3. 전수 조사 알고리즘 코딩을 하다보면 전수 조사에 대해 매우매우 반감을 가지게 되는데, 두려움 없이 해봐야 한다는 점…!!!

모두 파이팅!’