[백준 15685][C++] 드래곤 커브 (Gold 4)

이 문제는 아예 전혀 푸는 방법을 몰랐다.

 

블로그 참고

1. 각 세대별 선분이 그어지는 방향의 규칙을 찾아라

2. 그 규칙에 따라 입력값으로 주어지는 데이터에 대해 선분을 긋고

3. count 

 

https://yabmoons.tistory.com/60

 

---

[문제보기]

 15685. 드래곤 커브

[풀이과정]

이 문제에서 제시하는 조건에 맞춰서 세대별 드래곤 커브를 만들면,

0세대 : →

1세대 : → ↑

2세대 : → ↑ ← ↑

3세대 : → ↑ ← ↑ ← ↓ ← ↑

이렇게 화살표가 그려지는데, 잘 살펴보면 규칙성이 있는 것을 알 수 있다.

1세대는 0 세대의 화살표 + 그 화살표를 반시계 방향으로 90도 돌렸다.

그리고 2세대는 1세대의 화살표 + 1세대의 마지막부터 첫 번째 순서까지 반시계 방향으로 90도 돌린 화살표

 

따라서, 규칙은 전 세대 화살표 + 전 세대 화살표의 마지막 순번부터 첫 번째 순번까지 화살표들을 반시계

방향으로 90도 돌린 것의 집합이 된다.

 

필자는 각각 드래곤 커브의 수마다 계산을 해주었고, dragon() 함수를 만들었다.

 

dragon(int x, int y, int d, int g)

-> 이 함수는 vector direction을 이용해 드래곤 커브의 방향을 만들어 줄 건데, 세대별로 현재의 direction의 크기만큼

마지막 순번부터 처음 순번까지 반시계 방향으로 화살표를 돌려주어 direction에 저장해준다.. 이때, 반시계 방향으로

돌리는 연산은 calculation() 함수를 이용했다. 그러고 나서 각 좌표를 계산하여 map[][] 배열에 1로 채워준다.

 

마지막으로, map[][] 배열을 돌면서 정사각형이 만들어지는 부분을 찾고 ans를 1 증가해 준다.

[소스코드]

#include <iostream>
#include <vector>
using namespace std;
int n, ans = 0;
int map[101][101] = {0};
pair<int, int> dir[4] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};

void all_print(){
    cout << "\n";
    for(int i=0; i<11; i++){
        for(int j=0; j<11; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

int calculation(int d){
    return d+1 > 3 ? 0 : d+1;
}

void dragon(int x, int y, int d, int g){
    vector<int> direction;

    direction.push_back(d);
    for(int i=0; i<g; i++){
        int size = direction.size();
        for(int j=size-1; j>=0; j--){
            int d = calculation(direction[j]);
            direction.push_back(d);
        }
    }

    map[y][x] = 1;
    int nexty, nextx;
    for(int i=0; i<direction.size(); i++){
        nexty = y + dir[direction[i]].first;
        nextx = x + dir[direction[i]].second;

        if(nexty < 0 || 100 < nexty || nextx < 0 || 100 < nextx) continue;

        map[nexty][nextx] = 1;
        y = nexty;
        x = nextx;
    }

}

int main(){
    cin >> n;

    int x, y, d, g;
    for(int i=0; i<n; i++){
        cin >> x >> y >> d >> g;
        dragon(x, y, d, g);
    }

    all_print();

    for(int i=0; i<101; i++){
        for(int j=0; j<101; j++){
            if(map[i][j] == 1 && map[i+1][j] == 1 && map[i][j+1] == 1 && map[i+1][j+1] == 1){
                ans++;
            }
        }
    }

    cout << ans;
}

 

[해결 과정 중 실수한 부분]

8월 25일에 못 풀고 다시 푼 문제이지만, 드래곤 커브의 규칙성을 찾느라 손으로 썼다 지웠다를 좀 했다.