백준 15684 사다리조작 브루트포스로 풀기

목표: 백준 온라인 저지 : 15674 사다리조작 문제해결

환경: mac OS High Sierra 10.13.4, CLion

이 문제 또한 완전탐색으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요. 단점은 문제의 조건에 따라 오래 걸린다는 것인데, 이것을 최적화 하는 방법들이 있어요. 가지치기라든지 백트래킹이라든지

로직

크게 두가지로 나뉩니다. 사다리 두기, i번째 사다리 상단 출발해서 i번째 사다리 하단으로 도착하는지 체크하기

  1. 사다리 두기 0,0부터 시작해서 N-1,H-1 까지 main함수에서 가능한 애초에 둘 사다리 개수를 가지고 go함수를 들어갑니다. go함수 내부에 2중 for문 돌면서 둘 수 있는 공간에 사다리를 둡니다.

문제의 조건이 행의 수: 2<= N <= 10 열의 수 1 ≤ H ≤ 30 이므로 최대 배열크기가 300인 애들을 확인해보면 되요. 사다리가 0개인 경우 300C0, 사다리가 1개인 경우 300C1, 2개인 경우 300C2 .. 최대 3개니까 300C3

사다리 두기 : 300299298/ 321 = 약 4백만 충분히 모든 경우의 수를 다 다룰 수 있습니다.

여기서 제가 처음 설계해서 시간초과 나온코드에는 사다리를 두기전에 가능한 경우인지 체크하잖아요.

if(!map[i][j] && !map[i][j-1] && !map[i][j+1]){ 

이렇게 O(1) 만에 할 수 있는데, 해당하는 1차원 배열을 다 돌았어요. 그래서 이 문제 이후에는 보통 이런 체크로직에서 시간복잡도를 줄일 수 있는지 설계할때부터 생각을 하게 되었습니다.

그리고 항상 사다리 두고 재귀함수 호출한 후에, 재귀함수가 끝나면 for문으로 해당 열을 다 돌면서 사다리 둘지 보잖아요.

for문의 다음 인덱스에 사다리 둘 것이기 때문에 재귀함수 끝났으면 재귀함수 호출 전에 두었던 사다리를 제거하는 코드가 꼭 들어가야됩니다.(백트래킹이죠.)

그리고 만약에 시뮬레이션(i번째 사다리 상단에 출발해서 i번째 사다리 하단에 도착하는지 체크)이 성공하면 더이상 사다리를 두지않고 종료해버리기 때문에 300Cn 이 온전히 계산되지 않죠.

그래서 시간복잡도 계산한것보다 훨씬 빠르게 프로그램이 수행될겁니다. 전체의 경우의 수만큼 두다가 되면 그만 둬버리니까요.

  1. 시뮬레이션(i번째 사다리 상단에 출발해서 i번째 사다리 하단에 도착하는지 체크) 2중 for 돌기때문에 수행되는 시간복잡도 O(N^2) = 300 그러나 시뮬레이션 중에 하나라도 틀리면 나가리기 때문에 break 코드가 들어가서 온전히 O(N^2)이 절대 나올 수 없습니다.

여기서 중요하게 생각했던 부분은 시간복잡도가 1억번이하다. 무식하지만 안전한 방법이 됩니다.

사다리조작

[code]

#include <cstdio>
#include <climits>

const int MAXROW = 30;
const int MAXCOL = 10;

bool map[MAXROW+1][MAXCOL+2]; //좌우 패딩
int N,M,H; //열의수, 주어진 사다리 수, 행의 수
int ans = INT_MAX;
int recur;

bool simulate(){
    bool ret = false;
    int corret = 0, copy = 0;
    int j = 1, i = 1;
    for (j = 1; j <= N ; ++j) { // 열 반복
        copy = j;
        for (i = 1; i <= H; ++i) { //행 반복
            if(map[i][copy]){
                copy++;
            }else if( map[i][copy-1]){
                copy--;
            }
        }
        if(copy == j){
            corret+=1;
        }else{
            break;  //하나라도 다르면 의미없음.
        }
    }
    if(corret == N){
        ret = true;
    }

    return ret;
}

void go(int rowPos, int cnt, int goal){
    // rowPos부터 사다리 cnt를 추가하여 i번째 열이 사다리 타고 i번째로 갔는지 확인하는 함수

    if( cnt == goal){
        if(simulate()){
            ans = cnt;
        }
        return;
    }else{
        for (int i = rowPos; i <= H ; ++i) { // 행 반복
            for (int j = 1; j < N ; ++j) { // 열 반복 마지막 열에는 사다리 추가의미 없
                if(!map[i][j] && !map[i][j-1] && !map[i][j+1]){
                    map[i][j] = true;
                    if(ans != INT_MAX){
                        return;
                    }
                    go(i, cnt+1, goal);

                    map[i][j] = false;
                }
            }
        }
    }
}

int main() {

    scanf("%d %d %d", &N, &M, &H);

    for (int i = 0; i < M ; ++i) {
        int a,b;
        scanf("%d %d", &a, &b);
        map[a][b] = true;
    }

    for (int i = 0; i < 4; ++i) {
        go(1,0,i);
        if( ans != INT_MAX){
            break;
        }
    }

    if( ans == INT_MAX){
        ans = -1;
    }
    printf("%d\n", ans);


    return 0;
}