[백준] 골드4 15685번 - 드래곤커브 (C++)

문제 이해

드래곤 커브의 좌표와 방향, 세대가 주어진다.

모든 드래곤 커브의 흔적을 2차원 배열 위에 1로 표시한다.

사각형 모양의 1을 찾아 세면 문제 해결.

 

접근

1. 드래곤커브가 세대가 바뀔 때 기존 커브를 회전시키면서 좌표를 찍는다.

2. 0,0 ~ 99, 99 까지 arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] 이 4 인 곳을 모두 센다.

 

 

풀이

1. 드래곤 커브의 구현

x,y 좌표를 담을 빈 벡터를 선언하고 "초기 좌표" 와 "초기 좌표로부터 주어진 방향으로 이동한 좌표" 를 넣는다.

좌표 기준 90도 회전 알고리즘은 다음과 같다.

기준 좌표 sa, sb 와 회전할 좌표 ca,cb, 회전한 좌표 na, nb가 있다.

먼저 원점으로 이동시키기 위해 ca -= sa, cb -= sb를 해준다.

na = cos 90 * ca - sin 90 * cb, nb = cos90 * cb + sin 90 * ca 이다.

즉 na = -cb, nb = ca 이다. 회전 이후에 다시 좌표로 되돌려 주기 위해 na += sa, nb +=sb 를 수행하면 완성이다.

회전 알고리즘을 정리하면,

 

ca = vector[i].first;

cb = vector[i].second;

sa = vector.back().first;

sb = vector.back().second;

 

ca -= sa, cb -= sb;

na = -cb, nb = ca;

na += sa, nb += sb;

vector.push_back({na, nb});

 

이와 같다.

 

이 것을 기준 좌표를 제외한 벡터 내의 요소에 적용하여 다시 벡터에 담아야한다.

기준 좌표는 벡터의 맨 마지막 원소가 되어야한다.

따라서, 벡터의 맨 마지막 원소의 전 원소부터 0 (vector.size() - 2 ~ 0) 까지 순회하여 알고리즘을 적용한다.

그래야 순서가 맞게 벡터에 담긴다.

 

2. "크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력"

그냥 0,0 부터 99, 99 까지 4개의 좌표(정사각형 모양) 가 모두 1인 곳을 찾아서 모두 세면 된다. 

 

 

 

 

#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#include <string>
#include <queue>


using namespace std;
int N,M, L, R;

int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; // x y 기준


int answer = 0; 
void DragonCurve(vector<vector<int>> &map, int a, int b, int d, int gen){
    vector<pair<int, int>> dragonPos;

    // 0세대 드래곤의 좌표 담기
    dragonPos.push_back({a, b});
    dragonPos.push_back({a + dir[d][0], b + dir[d][1]});

    for(int i = 0; i < gen; i++){
        int sa = dragonPos.back().first;
        int sb = dragonPos.back().second;
        int dSize = dragonPos.size(); // 회전 전의 벡터 사이즈
        for(int j = dSize - 2; j >= 0; j--){ // 90도 회전
            int ca = dragonPos[j].first;
            int cb = dragonPos[j].second;
            ca -= sa;
            cb -= sb;

            int na = -cb;
            int nb = ca;
            
            na += sa;
            nb += sb;
            dragonPos.push_back({na, nb});
        }
    }
    

    for(int i = 0; i < dragonPos.size(); i++){
        //cout << dragonPos[i].first << "," << dragonPos[i].second << " ";
        //조건에 부합하면 배열에 1 대입
        if(dragonPos[i].first >= 0 && dragonPos[i].first <= 100
        && dragonPos[i].second >= 0 && dragonPos[i].second <= 100){
            map[dragonPos[i].first][dragonPos[i].second] = 1;
        }
    }
    //cout << '\n';
}

int main(){
    cin >> N;
    vector<vector<int>> map(101, vector<int>(101, 0));
    vector<pair<pair<int, int>, pair<int, int>>> dragon;
    for(int i = 0; i < N; i++){
        int a, b, d, gen;
        cin >> a >> b >> d >> gen;
        dragon.push_back({{a, b}, {d, gen}});
    }

    for(int i = 0; i < dragon.size(); i++){
        DragonCurve(map, dragon[i].first.first, dragon[i].first.second,
             dragon[i].second.first, dragon[i].second.second);
    }

    // 1-square check
    for(int i = 0; i <= 99; i++){
        for(int j = 0; j<= 99; j++){
            if(map[i][j] + map[i + 1][j] + map[i + 1][j + 1] + map[i][j + 1] == 4)
                answer ++;
        }
    }

    cout << answer <<'\n';
    return 0;
}