[algorithm] 백준 - 사다리 조작

삼성 SW 기출 문제이다. brute force와 구현문제이다.

 

간단히 설명하자면,

사다리 타기 게임인데, 각 세로줄이 게임을 완료한 후에도 동일한 위치에서 끝나야한다.

참고로 사다리의 가로줄은 맞닿을 수 없다.

 

사다리 원번호 num, 현재 번호 pnum, 직전에 탄 사다리 좌표 a,b에 대한 자료형을 만들었다.

 

struct width{
    int a,b;
};
struct ladder{
    width w;
    int number,pnumber;
};

 

 

사다리 타기 전, a는 0으로, b는 num, pnum은 num으로 초기화한다.

 

사다리 이동 방식

1. pnum과 b가 동일하거나, pnum - 1이 b와 동일할 경우,

그리고 직전에 탐색했던 가로 좌표가 아닐 경우,

직전에 탐색했던 a보다는 크지만 그 중에서 가장 작은 a를 찾는다.

 

2. 해당 a를 찾은 경우 직전에 탄 사다리 좌표 a와 b를 갱신시킨 뒤, 아래를 수행한다.

 

2 - 1. pnum과 b가 동일한 경우,

사다리 번호 pnum은 b + 1로 갱신된다.

 

2 -2. pnum - 1이 b와 동일할 경우,

사다리 번호 pnum은 b로 갱신된다.

 

1부터 다시 반복한다.

 

3. 해당 a가 없을 경우 break문으로 무한 루프를 빠져나온다.

 

void move(int index){
    while(1){
        bool isMovable = false;
        int pnumber = ladderVector[index].pnumber;
        int number = ladderVector[index].number;
        int laddera = ladderVector[index].w.a;
        int ladderb = ladderVector[index].w.b;
        int minA = h;
        int minB = 0;
        for(int i = 0; i < widthVector.size(); i++){
            int a = widthVector[i].a;
            int b = widthVector[i].b;
            if((pnumber == b || pnumber - 1 == b) && laddera < a && a <= minA){
                if(laddera == a && ladderb == b) continue;
                minA = a;
                minB = b;
                isMovable = true;
            }
        }
        if(isMovable){
            if(pnumber == minB){
                    ladderVector[index].pnumber = minB + 1;
            }
            else{
                ladderVector[index].pnumber = minB;
            }
                ladderVector[index].w.a = minA;
                ladderVector[index].w.b = minB;
        }
        else break;
    }
}

 

사다리 타기를 수행완료 후, 다시 또 사다리 타기를 수행해야하므로

사다리를 타기 전 상태로 초기화한다.

 

void allLadderInit(){
    for(int i = 0; i < n; i++){
        ladderVector[i].pnumber = ladderVector[i].number;
        ladderVector[i].w.a = 0;
        ladderVector[i].w.b = 0;
    }
}

 

만일 사다리에 가로 줄을 추가하지 않았음에도 결과로 사다리 원래 번호와 현재 번호가 동일할 경우,

dfs 작업을 수행하지 않고 0을 프린트 후 종료한다.

그렇지 않은 경우 dfs 작업을 수행한다.

 

이미 추가가 되어있는 가로줄일 경우 다음 index로 탐색을 진행한다.

그렇지 않은 경우, 사다리에 가로줄을 추가한다.

추가와 동시에 move함수를 호출하여 사다리를 탄 후,

사다리 원래번호와 현재 번호가 동일한지 확인했을 때,

동일하다면 가로줄 추가 수를 기록하여 가장 작은 수인지 확인한다.

그리고 사다리에 가로줄을 추가하는 함수를 재귀적으로 호출한다.

 

참고로 사다리에 가로줄을 추가할 때, 동일 작업을 수행하는 행위를 피하기 위해,

index를 기록해두고 그 index 다음을 탐색하도록 유도해야한다.

 

void dfs(int count, int index){
    if(count > 3){
        return;
    }
    for(int i = index; i < n; i++){
        for(int j = 1; j <= h; j++){
            if(visited[j][i]) continue;
            if(i - 1  > 1 && visited[j][i - 1]) continue;
            if(i + 1 < n && visited[j][i + 1]== true) continue;
            visited[j][i] = true;
                width w;
                w.a = j; w.b = i;
                widthVector.push_back(w);
                allLadderMove();
                if(allLadderCheckSame()){
                    minNum = min(minNum,count);
                }
                allLadderInit();
                dfs(count + 1,i);
                widthVector.pop_back();
                visited[j][i] = false;
        }
    }
}

 

전체적인 코드는 이렇다.

 

//사다리 조작
#include <iostream>
#include <vector>
using namespace std;

struct width{
    int a,b;
};
struct ladder{
    width w;
    int number,pnumber;
};
int minNum = 5;
vector<ladder> ladderVector;
vector<width> widthVector;
int n,m,h;
bool visited[31][10];
void move(int index){
    while(1){
        bool isMovable = false;
        int pnumber = ladderVector[index].pnumber;
        int number = ladderVector[index].number;
        int laddera = ladderVector[index].w.a;
        int ladderb = ladderVector[index].w.b;
        int minA = h;
        int minB = 0;
        for(int i = 0; i < widthVector.size(); i++){
            int a = widthVector[i].a;
            int b = widthVector[i].b;
            if((pnumber == b || pnumber - 1 == b) && laddera < a && a <= minA){
                if(laddera == a && ladderb == b) continue;
                minA = a;
                minB = b;
                isMovable = true;
            }
        }
        if(isMovable){
            if(pnumber == minB){
                    ladderVector[index].pnumber = minB + 1;
            }
            else{
                ladderVector[index].pnumber = minB;
            }
                ladderVector[index].w.a = minA;
                ladderVector[index].w.b = minB;
        }
        else break;
    }
}
void allLadderMove(){
    for(int i = 0; i < n; i++){
        move(i);
    }
}
bool allLadderCheckSame(){
    for(int i = 0; i < n; i++){
        if(ladderVector[i].number != ladderVector[i].pnumber){
            return false;
        }
    }
    return true;
}
void allLadderInit(){
    for(int i = 0; i < n; i++){
        ladderVector[i].pnumber = ladderVector[i].number;
        ladderVector[i].w.a = 0;
        ladderVector[i].w.b = 0;
    }
}
void dfs(int count, int index){
    if(count > 3){
        return;
    }
    for(int i = index; i < n; i++){
        for(int j = 1; j <= h; j++){
            if(visited[j][i]) continue;
            if(i - 1  > 1 && visited[j][i - 1]) continue;
            if(i + 1 < n && visited[j][i + 1]== true) continue;
            visited[j][i] = true;
                width w;
                w.a = j; w.b = i;
                widthVector.push_back(w);
                allLadderMove();
                if(allLadderCheckSame()){
                    minNum = min(minNum,count);
                }
                allLadderInit();
                dfs(count + 1,i);
                widthVector.pop_back();
                visited[j][i] = false;
        }
    }
}
int main(void){
    cin >> n >> m >> h;
    for(int i = 0; i < m; i++){
        width w;
        cin >> w.a >> w.b;
        widthVector.push_back(w);
        visited[w.a][w.b] = true;
    }
    for(int i = 1; i <= n; i++){
        ladder l;
        l.number = l.pnumber = i;
        l.w.a = l.w.b = 0;
        ladderVector.push_back(l);
    }
    allLadderMove();
    if(allLadderCheckSame()){
        cout << 0;
    }
    else{
        allLadderInit();
        dfs(1, 1);
        if(minNum == 5) cout << -1;
        else cout << minNum;
    }
}