백준 15685 드래곤 커브

선분이 이전 모양의 90도 회전한 모양이 덧붙는 형식입니다.

 

저는 그냥 그림을 보다가 이전세대 모양이 90도 회전하여 붙는 것이므로 이전 세대의 끝점에서 뒤로 가며 나오는 방향의 90도 회전한 방향의 좌표를 추가해주는 식의 재귀함수로 세대를 구한다음 체크하였습니다.

 

사각형의 개수는 각좌표의 4방향이 모두 1이면 체크 해주는 식으로 진행을 하면 됩니다.

 

다음은 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;

int visited[110][110];

void check(vector<pair<int,int> > dir, int cnt) {

    if(cnt == 0) {
        for(int i = 0; i < dir.size(); i++) {
            int x = dir[i].first;
            int y = dir[i].second;
            visited[x][y] = 1;
        }
        return;
    }

    int len = dir.size()-1;
    for(int i = len-1; i >= 0; i--) {
        int prevx = dir[i+1].first;
        int prevy = dir[i+1].second;
        int curx = dir[i].first;
        int cury = dir[i].second;

        int posx = dir.back().first;//붙일 기준이 되는 좌표
        int posy = dir.back().second;

        if(prevx-curx == 1) {
            if(posy-1 >= 0)
                dir.push_back({posx, posy-1});
        }
        else if(prevx-curx == -1) {
            if(posy+1 <= 100)
                dir.push_back({posx, posy+1});
        }
        else if(prevy-cury == 1) {
            if(posx+1 <= 100)
                dir.push_back({posx+1, posy});
        }
        else if(prevy-cury == -1) {
            if(posx-1 >= 0)
                dir.push_back({posx-1, posy});
        }
    }
    check(dir, cnt-1);
    return;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    int ans = 0;

    for(int i = 0; i < N; i++) {
        int x,y,d,g; cin >> x >> y >> d >> g;
        vector<pair<int,int> > cur;
        cur.push_back({x,y});
        if(d==0) cur.push_back({x+1,y});
        else if(d==1) cur.push_back({x,y-1});
        else if(d==2) cur.push_back({x-1,y});
        else if(d==3) cur.push_back({x,y+1});
        check(cur, g);
    }

    //최종 검사
    for(int i = 0; i <= 100; i++) {
        for(int j = 0; j <= 100; j++) {

            if(visited[i][j] == 1 && visited[i+1][j] == 1 &&
               visited[i][j+1] == 1 && visited[i+1][j+1] == 1) {
                ans++;
            }
        }
    }
    cout<<ans;

    return 0;
}