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

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

특별한 알고리즘이랄 것이 필요하지 않은 전형적인 시뮬레이션 문제였다.

하지만 설계를 제대로 하고 들어가지 않으면 꽤 해맬 수 있었던 문제이다.

여느 시뮬레이션 문제들이 그러하듯이, 상황을 어떻게 표현할 것인가 생각해야 한다.

나는 주의 깊게 그림을 살펴보지 않아서 간과했던 사실이지만, 문제 설명에서 그림을 보여주면서 좌표 값을 그림 아래에 표시해줬다.

그것을 보면, 커브의 상태를 좌표에 찍을 수 있고, 좌표에 어떻게 찍히느냐는 기본적으로 세대가 결정하고,

같은 세대라고 할지라도 시작한 방향값이 다르다면 다르게 찍힌다는 것을 알 수 있다.

(0,0)에서 시작한 0세대 커브는 (1,0)으로 x값이 1증가한다.

그리고 이어서 2세대로 변천할 때, 1세대의 마지막 점(1,0)에서 (1,-1)로 이동하여 y좌표가 1감소하는 것을 알 수 있다.

이 상황은 0,0에서 시작한 d값이 1인 0세대의 커브이다.

만약 나머지 조건이 동일하고, 방향 값인 d값이 1이었다면?  0,0에서 시작한 커브는 상단으로 뻗었을 것이고

0세대 커브는 0,0에서 0,-1로 변천했을 것이다. 이런식으로 파악해나가야 한다.

방향이 0인 세대별 커브의 성분을 방향 숫자로 나타내보면,

0세대: 0

1세대: 0, 1

2세대: 0, 1, 2, 1

3세대: 0, 1, 2, 1, 2, 3, 2, 1

4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1

...

이런식으로 증가한다. 여기서 규칙을 확인할 수 있다. 먼저 개수가 2의 거듭제곱 꼴로 늘어나고 있다.

그리고 문제에서 주어진 조건과 연결해서 확인해보면, 이전 세대의 커브를 90도 돌리고 끝을 붙인다고 했다.

90도 돌린다는 것은 방향값의 변화를 의미하는 것이고, 끝을 붙인다는 것은, 성분을 뒤에서부터 하나씩 붙인다는 것이다.

따라서 0세대에서 1세대로 갈 때, 0에 1을 더한 1이 붙은 것이고, 1세대에서 2세대로 갈 때, 1세대의 마지막인 1에 1을 더한 값인 2가 붙고, 0에 1을 더한 값인 1이 그 뒤에 붙은 것이다.

이를 그냥 배열 인덱스로 조절해서 구해도 되겠지만 동작 구조가 스택과 같으니, 스택을 활용했다.

나는 방향 0의 드래곤커브의 10세대를 구해서 배열에 저장했다. 10세대를 구하면 곧, 앞부분에 0~9세대도 포함되어 있는 것이기 때문에 변형해서 사용하면 된다. 또한 방향 0의 값을 구해 놓았으니, 방향이 변하면 모든 성분을 더해줘서 방향을 바뀐 것처럼 사용하면 되고, %4를 통해 값이 4를 넘어가지 않도록 유지해줘야 하겠다.

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
stack<int> stk;
int map[101][101];
int d[1025]; //0~3방향, 0~10세대
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j <= (1 << (i - 1)) - 1; j++) {
            stk.push(d[j]); //이전 세대의 것을 스택에 넣고
        }
        for (int j = 1 << (i - 1); j <= (1 << i) - 1; j++) {
            d[j] = (stk.top() + 1) % 4;
            stk.pop();
            //1씩 증가하면서 pop하면서 이전 세대의 것에 붙이면 현재 세대의 것이 나옴
        }
    }
 
    for (int i = 0; i < n; i++) {
        int x, y, dir, gen;
        cin >> x >> y >> dir >> gen;
        map[y][x] = 1;
        for (int j = 0; j <= (1 << gen) - 1; j++) {
            if ((d[j] + dir) % 4 == 0) {
                x++; //갱신하면서 움직여야 반영됨
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 1) {
                y--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 2) {
                x--;
                map[y][x] = 1;
            }
            else if ((d[j] + dir) % 4 == 3) {
                y++;
                map[y][x] = 1;
            }
        }
    }
    
    int cnt = 0;
    for (int i = 0; i < 100; i++) { //생각 없이 n까지만 잡으면 안 되고, x, y 최대 범위만큼
        for (int j = 0; j < 100; j++) { 
            if (map[i][j] == 1 && map[i][j + 1] == 1 &&
                map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) cnt++;
        }
    }
    cout << cnt;
    return 0;
}