[C++] 15685: 드래곤 커브

from GPT (문제와 연관은 없음)

🖍️ 실패한 원인

• 드래곤 커브 구현 방법을 생각하는 과정에서 방향 변화에 규칙이 있을 것 같다고 유추는 하였으나,
• 규칙을 발견을 못했고, 공식으로 풀어내지 못함 ㅜㅜ (결국 답안을 보고 풀이했다...)

🔍 해결 방법

• 드래곤 커브 n세대는 드래곤 커브 n-1세대의 방향을 역순으로 해서, +1한 뒤(반시계 90도 회전) %4를 하면 된다.
• (x+1)%4까지는 계산해봤는데 역순일거라고 생각을 전혀 못했다.
• 회전을 하게되면 방향의 순서가 바뀌게 되어서 역순이 되는데 그걸 캐치를 못했다... 다음에 비슷한 문제가 나오면 생각해서 풀 수 있도록 잘 익혀두자!!

📇 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

const int SIZE = 101;
bool board[SIZE][SIZE] = {false,};

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

void drawDragonCurve(int x, int y, int d, int g) {
    vector<int> dirList = {d};
    for (int gen=0; gen<g; gen++) {
        vector<int> reverse;
        for (int i=dirList.size()-1; i>=0; i--) {
            reverse.push_back((dirList[i]+1)%4);
        }
        dirList.insert(dirList.end(), reverse.begin(), reverse.end());
    }
    board[y][x] = true;
    for (int dir : dirList) {
        y += dy[dir];
        x += dx[dir];
        board[y][x] = 1;
    }
}

int countSquares() {
    int cnt = 0;
    for (int i=0; i<SIZE-1; i++) {
        for (int j=0; j<SIZE-1; j++) {
            if (board[i][j] && board[i][j + 1] &&
                board[i + 1][j] && board[i + 1][j + 1]) {
                ++cnt;
            }
        }
    }
    return cnt;
}

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

    int n;

    cin >> n;
    for (int i=0; i<n; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        drawDragonCurve(x, y, d, g);
    }

    cout << countSquares() << '\n';

    return 0;
}