백준 15685 드래곤커브

<링크>

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

<소스코드>

#include<stdio.h>
#include<vector>
using namespace std;
int pan[101][101];
void check(int x, int y, int d, int g)
{
    vector<int> v;
    v.push_back(d);
    for (int i = 0; i < g; ++i)
    {
        int size = v.size();
        for (int j = size - 1; j >= 0; --j)
        {
            int dir = v[j];
            int toDir = (dir + 1) % 4;
            v.push_back(toDir);
        }
    }
    int size = v.size();
    pan[x][y] = 1;
 
    for (int i = 0; i < size; ++i)
    {
 
        int dir = v[i];
        switch (dir)
        {
        case 0:++x; break;
        case 1:--y; break;
        case 2:--x; break;
        case 3:++y; break;
        }
        pan[x][y] = 1;
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    while (N--)
    {
        int x, y, d, g;
        scanf("%d%d%d%d", &x, &y, &d, &g);
        check(x, y, d, g);
    }
    int ans = 0;
    for (int x = 0; x<100; ++x)
        for (int y = 0; y <100; ++y)
        {
            if (pan[x][y] && pan[x + 1][y] && pan[x][y + 1] && pan[x + 1][y + 1])
                ++ans;
        }
    printf("%d", ans);
}
 

<풀이>

그림처럼 이전세대의 선분 하나랑 다음세대의 선분 한쌍이 각각 관계가 있다.

시작점부터의 방향만을 리스트로 나타내면 다음과 같다. 

잘 보면 규칙성을 발견할 수 있다. 

기존 세대의 방향 맨 끝부터 봤을때 기존 방향에서 왼쪽으로 90' 꺾은 방향으로 다음세대의 방향이 결정된다.

①↑에서 ←

②←에서↓

③↑에서 ←

④→에서↑

이런 규칙으로 변한다. 근데 문제에서도 친절하게

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

라고 되어있기 때문에 다음방향 = (이전방향+1)%4 이 된다.

이런식으로 K세대까지의 방향만을 쫙 만들어놓은 후

시작점부터 해당좌표에 체크해준다.