백준 15685번 : 드래곤 커브

• 분류: 구현, 시뮬레이션

코드

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

bool coord[101][101];

class Point {
public :
    int x, y;
    Point() {x=0; y=0;};
    Point(int a, int b) : x(a), y(b) {}
public :
    Point next(int d) const {
        if(d==0) return {x+1, y};
        else if(d==1) return {x, y-1};
        else if(d==2) return {x-1, y};
        else return {x, y+1};
    };
    Point rotate(Point center) const {
        return {center.x+center.y-y, center.y-center.x+x};
    }
};

int main() {
    int n;
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        vector<Point> curve;
        Point first = Point(x, y);
        curve.emplace_back(first);
        curve.emplace_back(first.next(d));
        for(int gen=1 ; gen<=g ; gen++) {
            Point center = curve.back();
            vector<Point> newPoints;
            newPoints.reserve(curve.size());
            for(auto iter = curve.rbegin() ; iter!=curve.rend() ; iter++) {
                newPoints.push_back(iter->rotate(center));
            }
            curve.insert(curve.end(), newPoints.begin(), newPoints.end());
        }
        for(auto & iter : curve) {
            coord[iter.x][iter.y] = true;
        }
    }
    int count=0;
    for(int i=0 ; i<100 ; i++) {
        for(int j=0 ; j<100 ; j++) {
            if(coord[i][j] && coord[i+1][j] && coord[i][j+1] && coord[i+1][j+1]) {
                count++;
            }
        }
    }
    cout << count;
}

• 코멘트
  
  Point라는 클래스를 만들고, 이들을 담는 vector를 사용했다.
  0번째 세대에서는 주어진 점 (x,y)와 d에 따른 그 다음 점을 벡터에 넣어 준다. d에 따른 그 다음 점은 Point 클래스의 next 함수로 구해 준다.
  그리고 각 세대마다 점들을 추가하는데, 회전의 중심이 되는 점은 가장 마지막에 vector에 추가된 점이 된다. 그리고 역순으로 vector를 iterate하면서 회전시킨 새 점을 추가해 준다.
  회전하는 공식은 간단하다. (a,b)가 중심이고 (c,d)가 회전시킬 점이면 (a+b-d, -a+b+c)가 회전한 점이 된다.
  마지막 세대까지 점들의 추가가 끝나면, 각 점들을 bool 배열 coord[][]에 추가한 후 coord를 싹 탐색하며 사각형이 다 true인 개수를 구한다.