백준 15685번 드래곤 커브 - C++ 풀이

---

 

1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다.
2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다.

 

1. 다음 세대 드래곤 커브를 만들 때는, 최근에 생성된 순서로 점들을 회전시킨다.

 드래곤 커브는 이루는 점들을 생성된 순서로 배열에 담는 것으로 나타낼 수 있다. 다음 세대 드래곤 커브는 현재 세대의 끝점(가장 최근에 생성된 점)을 기준으로 90도 회전하므로, 배열 역순으로 점들을 회전시켜준다.

 

2. 주어진 드래곤 커브들을 시뮬레이션한 뒤 네 꼭짓점이 모두 드래곤 커브에 포함된 정사각형의 개수를 센다.

 1의 방법으로 주어지는 드래곤 커브들을 모두 시뮬레이션으로 생성한 뒤, 드래곤 커브에 속하는 좌표를 체크해 조건을 만족하는 정사각형의 개수를 세주면 된다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int N;
bool board[101][101];

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

struct Point {
    int x, y;
};

void generateDragonCurve(int x, int y, int d, int g) {
    vector<Point> v;
    
    v.push_back({x, y});
    v.push_back({x+dx[d], y+dy[d]});
    
    while (g--) {
        int sz = v.size();
        int ex = v.back().x;
        int ey = v.back().y;
        
        for (int i=sz-2; i>=0; i--) {
            // 끝점을 기준으로 평행이동
            int tx = v[i].x - ex;
            int ty = v[i].y - ey;
            
            // 시계방향 90도 회전
            swap(tx, ty);
            tx *= -1;
            
            // 다시 평행이동
            tx += ex;
            ty += ey;

            v.push_back({tx, ty});
        }
    }
    
    for (auto point: v) {
        board[point.x][point.y] = true;
    }
}

int countSquare() {
    int cnt = 0;
    
    for (int i=0; i<100; i++) {
        for (int j=0; j<100; j++) {
            if (board[i][j] && board[i+1][j] && board[i][j+1] && board[i+1][j+1]) cnt++;
        }
    }
    
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        generateDragonCurve(x, y, d, g);    
    }
    
    cout << countSquare();

    return 0;
}