드래곤 커브

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int K,ans;
int dx[4] = {1, 0, -1, 0}; // 동, 북, 서, 남
int dy[4] = {0, -1, 0, 1};
vector<pair<pair<int,int>,int>> v[20]; // 좌표, 뒤 좌표를 향하는 방향
map<pair<int,int>,bool> m;
int changeDIR(int d){
    d--;
    if(d<0) d+=4;
    return d;
}
int reverseDIR(int d){
    d += 2;
    if(d>3) d-=4;
    return d;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> K;
    for(int i=0;i<K;i++)
    {
        int x,y,d,g;
        cin >> x >> y >> d >> g;
        v[i].push_back({{y,x},d});
        // 0세대까지는 만들어주기
        if(g >= 0){
            int ny = y + dy[d];
            int nx = x + dx[d];
            int nd = reverseDIR(d);
            v[i].push_back({{ny,nx},-1});
            v[i][0].second = nd;
        }
        // 해당 세대 좌표 만들기
        for(int j=1;j<=g;j++)
        {
            int pre = v[i].size()-1;
            int tmp = v[i].size();
            for(int st=tmp-2;st>=0;st--)
            {
                int dir = changeDIR(v[i][st].second);
                int ny = v[i][pre].first.first + dy[dir];
                int nx = v[i][pre].first.second + dx[dir];
                v[i].push_back({{ny,nx},-1});
                v[i][pre].second = reverseDIR(dir);
                pre++;
            }
        }
        // 좌표평면에 그리기
        for(int j=0;j<v[i].size();j++)
        {
            auto cur = v[i][j];
            m[{cur.first.first, cur.first.second}] = true;
        }
    }
    // 사각형 검사
    for(int i=0;i<=100;i++)
        for(int j=0;j<=100;j++)
            if(m[{i,j}] and m[{i+1,j}] and m[{i,j+1}] and m[{i+1,j+1}]) ans++;
    cout << ans;
    return 0;
}

• 드래곤 커브의 세대 증가 로직
  • 드래곤 커브의 가장 마지막 점 인덱스를 pre에 저장
  • 마지막 점을 제외한 나머지 점에 대해서 방향정보(dir)를 가져온다
    (방향 정보 : 내 다음 점이 나를 보는 방향)
  • 가져온 방향 정보를 90도 회전시킨 후 pre를 통해 새로운 ny, nx를 구한다
  • 새로 구한 점을 삽입하고, pre에 해당하는 점은 방향정보가 새로 생겼으니 추가해준다
  • pre++로 다시 새로운 끝점을 가리키게 한다
  • 앞 순서를 반복!

• 느낀 점
  • auto 변수로 변수를 받는 경우 읽을수는 있지만, 쓸 수는 없다 (값 복사)
  • 끝 점을 제외한 나머지 점을 당시 마지막 좌표를 기준으로 90도 회전시키는게 핵심