[C++] 백준/BOJ - 15685 : 드래곤 커브

---

문제 이해 단계

 

https://www.acmicpc.net/problem/15685

설명이 좀 어렵게 되어있는 문제.
모양이 이상하고 좀 이상하게 돌린다.

세대라고 해서 결국 레벨 같은 건데,
세대가 올라갈수록 이전의 했던 모양이 시계방향으로 90도 돌아간 채로 추가된다.

그렇게 점점 좌표계에서 많아지는데, 이건 그림을 보는 것이 훨씬 편하다.

들어오는 입력 정보로는
드래곤 커브의 x좌표와 y좌표, 움직일 방향, 그리고 몇 세대인지이다.

이렇게 여러 개의 입력정보가 들어와 여러 드래건 커브를 형성할 때,
맵에서 1x1 정사각형이 총 몇 개 나오는지 구하는 문제.

 

---

문제 접근 단계

문제가 좀 많이 어지럽다.

해당 그림을 배열을 만져가며 그리기에는 무리가 있다.
드래곤 커브가 만들어지는 원리에 집중했다.

드래곤 커브는 이전 세대의 모양을 그대로 이용하는 것이고,
이전 세대의 모양이 그대로 남아있기 때문에 
어찌 보면 이미 만들어진 것에 대해서는 변하지 않는다.

이를 이용하면 어떠한 규칙을 찾을 수 있지 않을까?

그래서 힌트에 나와있는 그림을 이용해서
0세대 ~ 4세대까지 방향을 0~4의 숫자로 표기하여 나열해 봤다.

위 숫자는 힌트에 있는 예제 2번에 보라색 드래곤 커브의 방향을
각 세대로 끊어서 나타낸 것이다.

이렇게 보면 뭔가 보일까??
그럼 이번에는 재사용되었던 것을 빼고 새로운 것만 보자.

솔직히 이래도 안 보인다..

저것들의 공통점은 저 숫자들의 개수가 이전 세대의 개수와 동일하다는 것이다.

그래서 저 숫자들과 이전세대의 숫자 전부와의 연관성을 살펴보니 규칙을 알아냈다.

글로 표현하자면, 다음 세대의 새로운 방향은
이전 세대의 방향의 역순에 +1을 한 값이다.

3+1이 0인 이유는 방향 4는 없기 때문에 그다음인 0으로 돌아온 것이기 때문이다.

이제 이렇게 규칙성을 찾아냈다.
이제 이 규칙을 통해 코드를 구현해 보자.

 

 

---

문제 구현 단계

int map[101][101];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

// 드래곤 커브를 만드는 함수
void makeDragon(int sx, int sy, int dir, int gen){
    string genDir[21]; // 세대 별 방향을 담아 둘 배열
    map[sx][sy] = 1; // 출발 좌표도 1로 바꿈
    genDir[0] = dir; // 0 세대 일때

    // 1세대부터 시작
    for(int i = 1; i <= gen; i++){
        genDir[i] = genDir[i-1];
        for(int j = genDir[i-1].length()-1; j >= 0; j--){
            genDir[i].push_back((genDir[i-1][j]+1)% 4); // 방향이 총 0~3까지 존재
        }
    }

    int x = sx;
    int y = sy;

    // genDir에 저장된 방향을 순서대로 호출
    for(int i = 0; i < genDir[gen].length(); i++){
        int dir = genDir[gen][i];
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        map[nx][ny] = 1; // 이동 후 그 좌표를 1로 세팅
        x = nx;
        y = ny;
    }
}

드래곤 커브를 만드는 makeDragon 함수이다.
매개변수로 시작 좌표와 시작 방향, 그리고 세대를 받는다.

해당 방식은 약간 동적계획법과 닮아있는데,
3세대라고 하면 1세대부터 시작하여 3세대까지 구한다.

왜냐하면 3세대를 구하기 위해서는 이전세대의 정보가 필요하기 때문이다.

중간에 모듈러 연산을 4로 해주는 이유는 방향이 총 4개만 존재하고
값이 0,1,2,3 최대 3까지 밖에 존재하지 않기 때문이다.

나머지 부분은 코드상에서 전부 이해될 것 같아서 주석으로만 달아두겠다.

핵심적인 코드는 여기까지가 끝이고
이제 아래에 전체 코드를 올리고 끝내겠다.

#include <iostream>
#include <vector>
using namespace std;

int map[101][101];
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};

// 드래곤 커브를 만드는 함수
void makeDragon(int sx, int sy, int dir, int gen){
    string genDir[21]; // 세대 별 방향을 담아 둘 배열
    map[sx][sy] = 1; // 출발 좌표도 1로 바꿈
    genDir[0] = dir; // 0 세대 일때

    // 1세대부터 시작
    for(int i = 1; i <= gen; i++){
        genDir[i] = genDir[i-1];
        for(int j = genDir[i-1].length()-1; j >= 0; j--){
            genDir[i].push_back((genDir[i-1][j]+1)% 4); // 방향이 총 0~3까지 존재
        }
    }

    int x = sx;
    int y = sy;

    // genDir에 저장된 방향을 순서대로 호출
    for(int i = 0; i < genDir[gen].length(); i++){
        int dir = genDir[gen][i];
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        map[nx][ny] = 1; // 이동 후 그 좌표를 1로 세팅
        x = nx;
        y = ny;
    }
}
void solve(){
    int ans = 0;
    for(int i = 0; i <= 99; i++){
        for(int j = 0; j <= 100; j++)
        if(map[i][j] == 1 && map[i][j+1] == 1
         && map[i+1][j] == 1 && map[i+1][j+1] == 1) ans++;
    }
    cout << ans;
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> curve;
    for(int i = 0; i < N; i++){
        int v1, v2,v3, v4;
        cin >> v1 >> v2 >> v3 >> v4;
        vector<int> info = {v1,v2,v3,v4};
        curve.push_back(info);
    }

    for(int i = 0; i < curve.size(); i++){
        makeDragon(curve[i][1],curve[i][0],curve[i][2],curve[i][3]);
    }
    solve();

    
}

 

 

---

시행착오

아이디어를 생각해 내는 게 불가능했다 거의.
이런 생각을 어떻게 해내지?

처음에는 어떻게든 배열을 만져서 구현하려고 했는데, 말이 안 됐다.
처음에는 재귀함수로 해보려다가 말도 안 돼서 실패.. 접근조차 불가능했는데..

힌트를 조금 보고 나서는 그래도 순조롭게 풀렸다.
dp개념과 섞었는데 잘 풀렸던 것 같다.