[15685] 드래곤 커브

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

15685번: 드래곤 커브

<문제>

그림만 보다보면 답이 안보인다.

드래곤커브를 회전시키는거에 집중하지 말고, 드래곤커브의 방향의 규칙성을 파악해야 쉽게 풀린다.

예제의 순서대로 방향을 아래와 같이 정의하자.

우/상/좌/하 : 0 / 1 / 2 / 3

또한, 우리가 필요한건 1*1의 정사각형을 이루는 네 개의 점이 모두 드래곤커브의 '일부'인 경우의 수이므로,

세대나 방향같은 부가적인 정보는 굳이 맵에 담을 필요가 없다.

결과를 계산할때에는 특정 위치에 드래곤커브가 존재하는지, 존재하지 않는지에만 신경쓰면 된다.

그렇기에 map을 bool형으로 선언하고 아래와 같이 정답을 계산할 수 있다.

bool a[103][103];
for (i = 0; i < 100; i++) {        
    for (j = 0; j < 100; j++) {
        if (a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1])
            ans++;
    }
}

우상좌하(0123)에 맞게 dy[4], dx[4]를 넣어주고, 0세대 드래곤커브는 다음과 같이 표현된다.

bool a[103][103];
int dx[4] = { 0,-1,0,1 }, dy[4] = { 1,0,-1,0 };
 
a[x][y] = true;//0세대 시작
x = x + dx[d];
y = y + dy[d];
a[x][y] = true;//0세대 끝

역시 예제를 기준으로 보면 3세대까지의 방향은 아래와 같다.

0세대 : 0

1세대 : 0 (1)

2세대 : 0 1 (2 1)

3세대 : 0 1 2 1 (2 3 2 1)

숫자로 표현했지만, 어디까지나 이전의 세대를 회전하여 이어붙이는 방식이므로, 세대 하나가 늘어나면 방향도 두배로 늘어난다.

역시 그림을 생각해보자. 이전에 무슨 그림이 그려지던 간에, 모든 방향이 90도 회전하게 된다.

현재 방향 = (이전의 방향 + 1) % 4 로표현할 수 있다는 의미이다.

또한, 이전에 마지막으로 그렷던것을 다음에 이어서 그리는 형식이므로, 현재 세대는 이전의 세대의 방향데이터를 항상 역으로 참조하는 꼴이 된다.

3세대가 0 1 2 1 2 3 2 1 이라면, 4세대는 16개의 수이고 그 모든 숫자는 +1%4의 연산을 거치며, 역으로 써나간다.

곧, 0 1 2 1 2 3 2 1 ( 2 3 0 3 2 3 2 1 )의 형태가 될것이다.

 

 

결론적으로 이전에 만들어진 수열을 역으로 참조하며, +1을 하고 %4를 하며, 하나씩 이어붙이면 한세대가 진행된다.

<소스코드>

#include<stdio.h>
#include<vector>
using namespace std;
bool a[103][103];
int n, y, x, d, g, dx[4] = { 0,-1,0,1 }, dy[4] = { 1,0,-1,0 };//(x,y)
vector<int>v;
int main(void) {
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        v.clear();
        scanf("%d %d %d %d", &y, &x, &d, &g);
        a[x][y] = true;//0세대 시작
        x = x + dx[d];
        y = y + dy[d];
        a[x][y] = true;//0세대 끝
        v.push_back(d);
        for (j = 0; j < g; j++) {
            int cnt = v.size();
            for (int T = cnt - 1; T >= 0; T--) {//역방향
                int nextKey = (v[T] + 1) % 4;
                x = x + dx[nextKey];
                y = y + dy[nextKey];
                a[x][y] = true;
                v.push_back(nextKey);
            }
        }
    }
    int ans = 0;
    for (i = 0; i < 100; i++) {
        for (j = 0; j < 100; j++) {
            if (a[i][j] && a[i + 1][j] && a[i][j + 1] && a[i + 1][j + 1])
                ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

그림을 수로도 바꾸고, 바꾼 뒤에도 그림이라는걸 상기시켜야 역방향과 같은 아이디어가 떠오르는 문제였던 것 같다.