[C++] 백준 - 15684 : 사다리 조작

문제 링크

15684번: 사다리 조작

 

 

풀이 )

  사다리에서 'ㅏ' 모양과 'ㅓ'모양을 구분하기 위해 line배열에서 각각 1, 2로 저장했다.

  이후 DFS로 가로선을 추가할 수 있는 곳에 0개부터 3개까지 추가한다.(makeLine( ))

  가로선을 추가할 때, 중복을 제거하기 위해, curH, curN을 넘겨주었다. (중복을 제거하지 않는 경우 시간초과)

  climbing( )에서는 위에서부터 사다리를 타면서 가로선을 만나면 2개씩 교체를 해서 끝까지 내려간 후, 끝까지 도달했을 때 순서가 맞는지 확인한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

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

bool climbing(void){
    int arr[11] = {0, };
    for(int i = 1; i <= n; ++i)
        arr[i] = i;

    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= n-1; ++j){
            if(line[i][j] == 1)
                swap(arr[j], arr[j+1]);
        }
    }

    for(int i = 1; i <= n; ++i){
        if(arr[i] != i)
            return false;
    }
    return true;
}

bool makeLine(int cnt, int dst, int curN, int curH){

    if(cnt == dst)
        return climbing();

    bool ret;
    for(int i = 1; i <= h; ++i){
        if(i < curH)
            continue;
        for(int j = 1; j <= n-1; ++j){
            if(i == curH && j <= curN)
                continue;
            if(line[i][j] || line[i][j+1])
                continue;

            line[i][j] = 1;
            line[i][j+1] = 2;
            if(makeLine(cnt+1, dst, j, i))
                return true;
            line[i][j] = 0;
            line[i][j+1] = 0;
        }
    }
    return false;
}

int main(void){
    cin >> n >> m >> h;
    while(m--){
        int a, b;
        cin >> a >> b;
        line[a][b] = 1;
        line[a][b+1] = 2;
    }

    for(int i = 0; i < 4; ++i){
        if(makeLine(0, i, 0, 0)){
            cout << i << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

 

주의 )

  가로선을 추가하는 과정에서의 중복 제거

  아래는 중복을 제거하지 않아 시간 초과한 코드다.

#include <iostream>
#include <algorithm>

using namespace std;

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

bool climbing(void){
    int arr[11] = {0, };
    for(int i = 1; i <= n; ++i)
        arr[i] = i;

    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= n-1; ++j){
            if(line[i][j] == 1)
                swap(arr[j], arr[j+1]);
        }
    }

    for(int i = 1; i <= n; ++i){
        if(arr[i] != i)
            return false;
    }
    return true;
}

bool makeLine(int cnt, int dst){

    if(cnt == dst)
        return climbing();

    bool ret;
    for(int i = 1; i <= h; ++i){
        for(int j = 1; j <= n-1; ++j){
            if(line[i][j] || line[i][j+1])
                continue;

            line[i][j] = 1;
            line[i][j+1] = 2;
            if(makeLine(cnt+1, dst))
                return true;
            line[i][j] = 0;
            line[i][j+1] = 0;
        }
    }
    return false;
}

int main(void){
    cin >> n >> m >> h;
    while(m--){
        int a, b;
        cin >> a >> b;
        line[a][b] = 1;
        line[a][b+1] = 2;
    }

    for(int i = 0; i < 4; ++i){
        if(makeLine(0, i)){
            cout << i << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;