[BOJ] 15685 : 드래곤 커브

15685 : 드래곤 커브

풀이

시뮬레이션

하라는대로 0세대를 만든 후 종점에서 나머지점을 시계방향으로 90도 회전 시키면 된다.

그런데 종점 기준으로 나머지점을 90도 회전시키지를 못하겠다.

종이에 적어보면서 규칙을 찾아보니까

종점에서 그 전의 정점의 회전값을 +1해서 이동하고 종점을 갱신해나가면

새로운 세대가 만들어지는 규칙이 있었다.

원하는 세대가 될때까지 반복하며 새로운 정점은 arr를 1로 만들어서 체크했다.

커브끼리 중첩되도 상관없고, 커브가 밖으로 나가는 경우가 안주어지기때문에 간단했다.

코드

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

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

void dragon(int x, int y, int d, int g) {
    //( (x,y좌표), 방향 )
    vector<pair<pair<int, int>, int>> v;
    v.push_back({ {x, y}, -1 });
    arr[x][y] = 1;
    int nx = x + dx[d];
    int ny = y + dy[d];
    v.push_back({ {nx,ny}, d});
    arr[nx][ny] = 1;
    //현재세대
    int curg = 0;
    while (curg < g) {
        vector<pair<pair<int, int>, int>> tmp = v;
        int cx = tmp.back().first.first;
        int cy = tmp.back().first.second;
        int nd = (tmp.back().second + 1) % 4;
        tmp.pop_back();
        while (!tmp.empty()) {
            int ncx = cx + dx[nd];
            int ncy = cy + dy[nd];
            v.push_back({ {ncx,ncy}, nd });
            arr[ncx][ncy] = 1;
            nd = ( tmp.back().second + 1 ) % 4;
            cx = ncx;
            cy = ncy;
            tmp.pop_back();
        }
        curg++;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int x, y, d, g;
    for (int i = 0; i < n; i++) {
        cin >> x >> y >> d >> g;
        //arr에 드래곤 커브만큼 1을 넣음
        dragon(y, x, d, g);
    }
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (arr[i][j] && arr[i + 1][j] && arr[i][j + 1] && arr[i + 1][j + 1])
                ans++;
        }
    }
    cout << ans;
    return 0;
}
Written on April 10, 2019