[백준 15685] 드래곤 커브, C++

https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

본 문제는 문제도 잘 이해되지 않고, 접근하기가 어려워 검색을 통해 힌트를 얻었다. 문제의 핵심은 다음과 같다.

첫 방향이 0이고 3세대인 경우는 (0), (0, 1), (0, 1, 2, 1), (0, 1, 2, 1, 2, 3, 2, 1)과 같은 규칙으로 드래곤 커브를 만들 수 있다. (0, 1)를 i번이라 하면  i+1번은 (i번 째) + (i번을 1씩 증가하고 뒤집는 경우) 가 된다. 따라서 먼저 각각의 드래곤 커브의 방향을 저장하고 시작점에서 방향에 맞게 이동하면 문제를 풀 수 있다.

구현 자체는 쉽지만 문제를 이해하고 핵심을 파악하는게 제일 어려운 문제라고 생각한다.

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool chk[101][101];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int x, y, d, g;
        scanf("%d %d %d %d", &x, &y, &d, &g);
        vector<int> a;
        a.push_back(d);
        for (int j = 0; j < g; j++) {
            vector<int> tmp;
 
            // 1씩 증가
            // 방향이 3까지 있으므로 4의 나머지 연산을 한다.
            for (int k = 0; k < a.size(); k++) {
                tmp.push_back((a[k]+1)%4);
            }
 
            // 뒤집고 이전 배열에 추가한다.
            reverse(tmp.begin(), tmp.end());
            for (int k = 0; k < tmp.size(); k++) {
                a.push_back(tmp[k]);
            }
        }
 
        // 시작점
        chk[x][y] = true;
 
        // 생성된 드래곤 커브의 방향에 맞게 움직인다.
        for (int j = 0; j < a.size(); j++) {
            x += dx[a[j]];
            y += dy[a[j]];
            chk[x][y] = true;
        }
    }
 
    // 1x1 정사각형의 네 꼭짓점이 드래곤 커브인 경우 확인
    int ans = 0;
    for (int i = 0; i <= 99; i++) {
        for (int j = 0; j <= 99; j++) {
            if (chk[i][j] && chk[i+1][j] &&
            chk[i][j+1] && chk[i+1][j+1]) ans += 1;
        }
    }
    printf("%d\n", ans);
}