백준 15685 드래곤 커브 (C++)

안유태·2023년 7월 7일
0

알고리즘

목록 보기
106/239

15685번: 드래곤 커브

좌표 위의 점의 이동을 구현하는 문제이다. 각 세대마다 이전 세대는 시계 방향으로 90도 회전시킨 후 끝 점에 이어 붙인다. 점을 90도 회전하는 공식은 (xcosθ - ysinθ, xsinθ + ycosθ)를 사용했다. 90도를 회전하므로 회전 후 좌표는 (-y, x)가 된다. 먼저 0세대 좌표부터 v에 넣어주고 남은 세대만큼 반복문을 돌아준다. 반복문을 돌며 회전 후의 좌표를 구해 v에 넣어주고 이를 반복한다. 이때 회전의 기준은 항상 이전 세대의 마지막 좌표가 되므로 회전 전에 (0,0)으로 옮기기 위해 빼주고 회전 후 다시 더해준다. 이 과정을 반복하며 좌표에 해당하는 위치를 A에서 true로 바꿔주고 4개의 꼭지점이 true인 것을 찾아 카운트해주었다.
생각보다 간단하게 풀 수 있었던 문제였다.



#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int x, y, d, g;
bool A[101][101];
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };

void solution() {
    vector<pair<int, int>> v;
    int ny = y + dy[d];
    int nx = x + dx[d];

    v.push_back({ y,x });
    v.push_back({ ny,nx });

    A[y][x] = true;
    A[ny][nx] = true;

    for (int i = 0; i < g; i++) {
        int size = v.size();
        int cy = v.back().first;
        int cx = v.back().second;

        for (int j = size - 2; j >= 0; j--) {
            int ty = v[j].first - cy;
            int tx = v[j].second - cx;

            int gy = tx + cy;
            int gx = -ty + cx;

            v.push_back({ gy,gx });
            A[gy][gx] = true;
        }
    }
}

void result() {
    int answer = 0;

    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (A[i][j] && A[i + 1][j] && A[i][j + 1] && A[i + 1][j + 1]) {
                answer++;
            }
        }
    }

    cout << answer;
}

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

    int N;
    cin >> N;

    while (N--) {
        cin >> x >> y >> d >> g;
        solution();
    }

    result();

    return 0;
}
profile
공부하는 개발자

0개의 댓글