BOJ 15685 [드래곤 커브]

BOJ 드래곤커브 : https://www.acmicpc.net/problem/15685

안녕하세요. 이번 문제는 백준 온라인 저지의 드래곤 커브입니다.

문제 해결방법은 다음과 같습니다.

1. 우선 각 방향에 맞게 0세대 드래곤 커브에 해당하는 점을 벡터에 저장.

2. 벡터에 저장된 마지막 점을 기준점으로 삼는다.

3. 기준점을 기준으로 벡터의 나머지 요소들을 회전변환.

4. 새로 구해진 드래곤 커브 내의 점을 벡터에 저장후, 해당 좌표의 Visited를 true로 변경. (주어진 세대가 끝날때까지 2~4 반복)

5. 네 꼭지점이 모두 true인 격자를 구한다.

#include <iostream>
#include <vector>
using namespace std;
bool Visited[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> curve_p;
    int pivot_x, pivot_y;
    for(int i=0; i<N; i++) {
        curve_p.clear();
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        curve_p.push_back(make_pair(y, x));
        pivot_y = y + dy[d];
        pivot_x = x + dx[d];
        Visited[y][x] = true;
        Visited[pivot_y][pivot_x] = true;
        curve_p.push_back(make_pair(pivot_y, pivot_x));
        for(int j = 1; j <= g; j++) {
            int size = (int)curve_p.size() - 1;
            pivot_y = curve_p[size].first;
            pivot_x = curve_p[size].second;
            for(int k = size-1; k >= 0; k--) {
                int next_y = pivot_y - pivot_x + curve_p[k].second;
                int next_x = pivot_y + pivot_x - curve_p[k].first;
                curve_p.push_back(make_pair(next_y, next_x));
                Visited[next_y][next_x] = true;
            }
        }
    }
    int result = 0;
    for(int i=0; i<100; i++)
        for(int j=0; j<100; j++)
            if(Visited[i][j] && Visited[i][j+1] && Visited[i+1][j] && Visited[i+1][j+1])
                result++;
    cout << result << endl;
    return 0;
}