백준 15685 드래곤 커브

정말 삽질을 많이 해서 배울 것이 많았던 문제이다..

정답률이 높아서 쉬울 거라고 생각했는데, 첫 접근부터 이상했기 때문에 4시간 동안 생각하고도 풀지 못해서 결국 인터넷에 검색해서 참조했다.

 

삽질 목록

1. 문제에 대한 접근이 잘 못 되었다.

 세대가 증가하면서 그려야 하는 방향이 역 방향으로 가는 구조임(현재 끝점이 3으로 왔고, 바로 앞의 점이 2 방향으로 왔다면, 다음에 그릴 점의 방향은 0이 되고, 그 다음 그릴 점의 방향은 3이 됨.)을 알았다.

하지만 그 전에 그리는 드래곤 커브를 vector에 일일히 저장하는 방식으로 풀려고 하다보니, stack을 사용하려 하지 않고, 어떻게든 만들어 놓은 vector를 사용하여 풀려고 했다.

그러다보니 코드가 복잡해졌고, 멘탈이 나가게 되었다.

=> 풀다가 코드가 복잡해지면 더 이해하기 쉽게 코딩할 수 있는지 생각해보자.

 

또한, 끝 점만 저장하고 있으면 다음에 올 점을 그릴 수 있지만, 모든 드래곤 커브를 다 저장해야 한다고 생각하였다. 문제를 어떻게 풀어야 할지 감은 잡았지만, 이를 풀 수 있는 방법의 선택이 잘못 되었던 것이다.

 

2.stack의 사이즈 조절 문제. 

 for문을 돌 때 stack.size()를 이용하여 돌렷는데, stack을 pop하면서 size가 변하는 것을 간과하여, 계속 이상한 답이 나오고 있었다. stack이나 queue를 사용함에 있어서 이를 주의해야 함을 다시 깨달았다.

 

3. 범위 문제

 항상 문제의 범위를 보고 주의하면서 풀고 있다고 생각했는데, 아무리 생각해도 더이상 틀린 코드가 아니라고 생각했음에도 틀렸다고 나와서 매우 당황했다.

그래서 혹시나 범위 문제인가 싶어서 봤더니 역시나 처음에 선언하는 100 x 100 배열의 범위를 잘못 잡았기 때문이었다. 범위는 2번, 3번 확인하도록 해야겠다.

 

4. 사각형의 개수를 세는 방법

 아주 멍청하게 풀었다. 나름대로 세는 방법을 생각했는데, 오히려 복잡하게 생각한 것이 화근이 되었던 것 같다. 이래서 알고리즘 문제 풀이는 경험이 중요한 것 같다.

그냥 왼쪽 위의 꼭짓점을 기준으로 잡고 4방향을 검사하면 되는 것인데, 처음에 사각형을 겹치게 셀 수 있다고 생각하여 꼭짓점을 -1, 0, 1로 주어 어렵게 풀려고 했었다.

혼쭐이 났지만 좋은 경험이 된 것 같다.

 

5. 이동 방향 문제

 bfs를 풀면서 int dr[4] = {-1,0,1,-1}; 과 같이 배열을 선언해놓고 사용했었다. 하지만 이를 그냥 암기식으로 사용했을 뿐 응용할 생각을 전혀 하지 못했다.

문제에 0일 때는 오른쪽 방향, 1일 때는 위쪽 방향 등이 주어졌는데, 이 때 0과 1같은 값을 dr의 index값으로 쓸 생각을 전혀 못했다. 그래서 switch문을 통해 매우 하드 코딩을 하였다.

또 끝 점이 0번 방향으로 왔을 때, 다음 점은 1번 방향이 되고, 1번은 2번, 2번은 3번, 3번은 0번이 됨을 알았다. 그럼에도 이를 수식으로 쉽게 나타낼 수 있을 거라는 생각만하고, 이를 찾을 생각을 하지 않았다.

(d+1)%4를 하면 위의 dr의 index로 사용하여 매우 짧은 코딩을 할 수 있음에도, 스스로 힘든 길을 걸어간 것이다.

이것도 앞으로 알고리즘 풀이에서 좋은 양분이 되었으면 좋겠다.

 

처음 말했듯이 이 문제가 나의 알고리즘 공부에 매우 큰 정신적 타격을 주었지만, 그만큼 큰 거름이 된 것 같아서 시간은 많이 썼지만, 보람있는 문제였다.

마지막으로, 앞서 정답을 맞췄던 문제들도 다시 리팩토링을 하면 많은 공부가 될 것 같다는 생각이 든다.

 

아래는 코드이다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
bool map[101][101];
int ans;
//0은 ->, 1은 위로, 2는 <-, 3은 아래로
int dr[4] = { 0, -1, 0, 1 };
int dc[4] = { 1, 0, -1, 0 };
 
//그림을 그리는 데 필요한 건 generation과 바로 직전 (r,c)와 direction이다.
void draw(int row, int col, int dir, int gener) {
    //direction은 역방향으로 필요하기 때문에 stack으로 만든다.
    stack<int> direction;
    direction.push(dir);
    //끝 점의 위치를 true로 바꾼다.
    map[row][col] = true;
 
    //세대를 증가시켜가면서 map에 점을 표시한다. i는 세대의 번호
    for (int i = 1; i <= gener; i++) {
        //세대가 증가하면 저장된 점의 수만큼 그려 줘야 한다.
        //기존의 dragon에 점들이 추가되는 것이므로 cp본을 만든다음 진행해야 한다.
        stack<int> cp_direction = direction;
        int size = cp_direction.size();
        //stack을 pop시키거나 push하면 stack.size()가 변하니까 이를 조심하자.
        for (int j = 0; j < size; j++) {
            //stack에서 direction을 꺼낸다.
            int d = cp_direction.top();
            cp_direction.pop();
 
            //끝 점을 바꿔준다.
            row = row + dr[(d + 1) % 4];
            col = col + dc[(d + 1) % 4];
            //다음 direction을 stack에 넣는다.
            direction.push((d + 1) % 4);
            if (row >= 0 && row < 101 && col >= 0 && col < 101)map[row][col] = true;
        }
        /*출력(디버깅)
        printf("\n------%d 세대 후 map-----------\n",i);
        for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
        printf("%2d ", map[i][j]);
        }
        printf("\n");
        }
        printf("\n---------------------------------\n");
        */
    }
}
 
int main(int argc, char** argv) {
    int n;
    cin >> n;
 
    //col, row 순으로 입력이 들어오는 것 조심.
    for (int i = 0; i < n; i++) {
        int r, c, d, g;
        scanf("%d %d %d %d", &c, &r, &d, &g);
        //시작점은 map에 바로 넣는다.
        map[r][c] = true;
        //끝 점을 인자로 주어서 바로 그린다.
        //0,1,2,3 방향에 맞춰서 dr, dc를 만드는 것이 중요하다.
        draw(r + dr[d], c + dc[d], d, g);
    }
 
    //사각형 개수 세기
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            //어렵게 생각할 필요 없이 사각형의 왼쪽 위 점을 기준으로 생각하면 된다. 그러면 세었던 사각형을 또 세는 일은 없다.
            //대신 주의 할 것은 100 x 100의 범위이다.
            if (map[i][j] == true) {
                if (map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])ans++;
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}

 

백준 강의에서 드래곤 커브 문제를 다루길래 먼저 다시 풀어 보았다.

0세대 일 때 시작점과 끝점만 미리 표기를 한 후, stack을 이용하여 드래곤 커브를 그렸다.

커브를 그릴 때에는 pop하면서 진행해야 하기 때문에 cp를 반들어서 이용하며, 새로 그린 점들의 dir은 원본 stack에 저장한다.

세대가 증가할 때 마다 cp stack을 새로 생성해야 한다.

앞 번 코드보다는 많이 리팩토링된 것 같다.

#include <iostream>
#include <stack>
using namespace std;
 
int n, x, y, d, g;
bool map[101][101];
 
int dr[4] = { 0,-1,0,1 };
int dc[4] = { 1,0,-1,0 };
 
void solve(int row, int col, int dir, int gener) {
    stack<int> st;
    //시작점을 map에 표시하고 dir을 stack에 저장
    map[row][col] = true;
    st.push(dir);
    //0세대는 무조건 있으므로, 0세대의 끝 점으로 point를 이동하고, map에 표시
    //row, col로 그려야 할 점을 움직인다.
    row = row + dr[dir];
    col = col + dc[dir];
    map[row][col] = true;
    
    stack<int> cp_st;
    //세대의 수 만큼 그려줘야 한다.
    for (int i = 0; i < gener; i++) {
        //세대가 증가할 때마다 cp_stack이 empty되므로 while문을 설정한다.
        cp_st = st;
        while (!cp_st.empty()) {
            dir = cp_st.top();
            cp_st.pop();
            //다음 방향으로 바꿔준 후 stack에 넣는다.
            dir = (dir + 1) % 4;
            st.push(dir);
            row = row + dr[dir];
            col = col + dc[dir];
            map[row][col] = true;
        }
    }
}
 
int main() {
    int ans = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> x >> y >> d >> g;
        solve(y, x, d, g);
        /*
        for (int x = 0; x < 20; x++) {
            for (int y = 0; y < 20; y++) {
                cout << map[x][y] << ' ';
            }
            cout << endl;
        }
        cout << endl;
        */
    }
 
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])ans++;
        }
    }
 
    cout << ans << endl;
 
    return 0;
}