백준 15684 사다리 조작

사진은 너무 많아서 일부만 가져왔다..

 

오늘도 돌아온 반성의 시간.. 뭘 잘못했는지 알아보자.

 

1. 나름대로 생각해서 어떻게 풀지 정한다음 코딩을 시작했다. 하지만 그 문제를 푸는 방식부터 잘못되었다.

즉, 생각은 했으나 그 방법으로 풀릴지 검증을 하지 않고 코딩을 시작한 문제이다.

 

처음에는 각 가로 사다리를 2차원 배열의 한 원소로 잡는 것이 아니라, 세로선과 가로선이 만나는 부분을 한 원소로 잡으려고 했다. 그래서 인접한 두 원소가 true이면 사다리가 있는 것으로 하려 했다.

하지만 이는 오른쪽으로 연속된 두 사다리를 체크할 때 힘들다.

1111과 같은 경우 사다리가 2개 있는 것인데 이를 구분할 방법이 없다.

 

그래서 생각한 것이 중간에 사다리가 있고 없고를 구분하기 위해서 111000과 같이 두어서 가로선과 세로선이 만나는 부분은 물론이고, 사다리의 여부까지 넣으려고 했다. 하지만 시간 초과가 뜨고 말았다.

 

2. 이처럼 가로선과 세로선이 만나는 곳을 원소로 잡은 이유는 직접 사다리를 타고 내려가는 것 처럼 좌표를 잡아서 각 세로선이 제자리를 찾아가는지 보려고 했기 때문이다.

즉 (0,0)에서 시작하여 사다리가 있을 경우 (0,1)로 변환 시킨 것이다. 매우 복잡한 방식이 아닐 수 없다.

 

이러한 풀이를 하게 된 원인은???

손으로 풀듯이 코딩을 하려 했기 때문이다. 하지만 복잡한 계산은 컴퓨터가 해준다. 나는 쉽게 풀 수 있는 방법을 컴퓨터에게 알려주기만 하면 된다. 그러면 어떻게 쉽게 풀 수 있을 것인가.

 

사실 여기까지 왔을 때 이미 4시간 정도 끙끙대고 있었기 때문에, 다른 분들의 코드를 참조했다.

그래서 잘못한 점을 찾아 내었다.

 

3. 먼저, 사다리를 놓는 배열을 잘못 설정하고 있었다. 사다리(가로선)이 들어갈 공간을 하나의 원소로 잡기만 해도 충분한데 쓸 데 없이 가로선과 세로선이 만나는 곳을 하나의 원소로 잡고 있었다.

쉽게 풀 수 있는 문제를 어렵게 푸는 멍청한 짓을 줄여야 겠다.

 

4. 다음으로 완전 탐색으로 찾아야 되며, 재귀를 이용해야 한다는 것은 알고 있었다. 하지만, 1차원 배열에 있는 것은 완전 탐색을 해보았으나 2차원 배월의 원소를 해본적은 없었다. 그래서 dfs안에서 2차원 배열을 계속 돌면서 사다리를 추가하고 빼다보니 시간 초과가 발생했다. 매 dfs마다 2차원 배열을 돌다보니 당연한 결과였다.

따라서, dfs의 인자로 좌표값을 넘겨주면서 완전탐색을 진행했다.

 

5. 마지막은 각 세로선은 각 자리를 찾아서 내려가기만 하면 되므로, column을 기준으로 +,-만 체크해주면 된다. 마지막 row에 도착했을 때 해당 column값과 같을 경우 제자리를 찾아온 것이기 때문이다.

 

6. 모든 풀이가 다 끝났는데 런타임 에러가 발생했다. 이유가 뭔지 찾아보다가 발견한 질문이 아래 링크에 있다.

여기

제자리를 찾은 경우 dfs 내에서 return을 통해 빠져나오기 힘들 것 같아서 exit 함수를 사용했는데, 아무 생각없이 인자로 1을 전달해 주었다. 하지만 위 링크에서 볼 수 있듯이 main이 0을 반환하듯이 exit의 인자로 0을 전달해야 했다.

 

그래도 점점 경험치가 쌓이고 있는 듯한 느낌이라서 힘들면서도 재밌는 것 같다.

코드는 아래와 같다.

#include <iostream>
#include <vector>
using namespace std;
 
bool labor[40][20];
 
int m, n, cnt;
 
//모든 세로선에서 사다리를 탄다. 가능하면 true
bool cal() {
    //(0,0)부터
    //모든 세로선을 돌면서
    for (int k = 1; k <= m; k++) {
        int c_r = 1;
        int c_c = k;
 
        while (c_r != n + 1) {
            if (labor[c_r][c_c]) {
                c_c++;
            }
            else if (labor[c_r][c_c - 1]) {
                c_c--;
            }
            c_r++;
        }
        //그대로면 true, 아니면 false
        if (c_c != k) return false;
    }
    return true;
}
 
void add(int idx, int row, int col, int ans) {
    /*출력(디버깅)
    printf("\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            printf("%d ", labor[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    */
 
    //모든 사다리를 다 만들어 봤으면 return
    if (row == n + 1 && col == 1)return;
    //cnt만큼 사다리가 추가되었을 때 사다리가 true인지 확인한다.
    if (idx == ans) {
        if (cal()) {
            printf("%d\n", ans);
            exit(0);
        }
        return;
    }
    //이미 있는 사다리면
    if (labor[row][col]) {
        //추가 사다리를 count 하지 않고, 다음 사다리로 넘어간다.
        if (col == m) add(idx, row + 1, 1, ans);
        else add(idx, row, col + 1, ans);
    }//없었던 사다리면 추가하고 다음 사다리로 넘어간다.
    else {
        //사다리를 한 개 추가해본다.
        labor[row][col] = true;
        if (col == m) add(idx + 1, row + 1, 1, ans);
        else add(idx + 1, row, col + 1, ans);
 
        //현재 사다리를 빼고 다음 사다리르 넣어본다.
        labor[row][col] = false;
        if (col == m) add(idx, row + 1, 1, ans);
        else add(idx, row, col + 1, ans);
    }
}
 
int main(int argc, char** argv) {
    int ans = 0;
    cin >> m >> cnt >> n;
 
    for (int i = 0; i < cnt; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        //가로선이 들어가는 공간을 하나의 원소로 잡는다.
        labor[a][b] = true;
 
        /*출력(디버깅)
        printf("\n-------------사다리 넣은 후 map----------\n");
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m * 2 - 1; y++) {
                printf("%d ", labor[x][y]);
            }
            printf("\n");
        }
        printf("\n------------------------------------------\n");
        */
    }
 
    for (int i = 0; i < 4; i++) {
        add(0, 1, 1, i);
    }
 
    printf("-1\n", ans);
 
    return 0;
}