[삼성 기출 문제] 백준15685 드래곤 커브

문제 링크

어떻게 풀까?

이 문제에서 문제를 풀기위해 생각해봐야 할 것이 2 가지 있습니다.

1. 세대가 올라갈때 선을 어떻게 연결할 것인가?

2. 네 꼭짓점이 드래곤 커브의 일부인 것은 어떻게 찾을 것인가?

1번부터 시작하겠습니다.

우선, 예제를 하나 보시죠!

(0,0)에서 3 세대인 그래프입니다.

일단, 선의 총 길이를 보겠습니다.

선의 길이는 이전 세대의 길이만큼 +됩니다!

n-1 세대 길이가 x 였다면, n세대의 선분 길이는 총 2*x가 되는 것이죠!

즉, 2의 제곱승으로 길이가 늘어납니다.

문제에서 최대 세대가 10세대까지이므로, 길이는 총 1024까지 될 것 입니다!

그럼 가장 중요한 점!

과연, n-1세대에서 n세대로 갈 때 어떻게 그려야 하는가? 입니다.

저 위의 그림에서 한 번 어떻게 그려야하는지 생각해 봅시다!

시작 위치는 (0,0)이고 처음 방향은 오른쪽 입니다!

2세대의 끝 점은 (0,-2) 입니다.

그리고 잘 보시면, (0,0) ~ (0,-2)로 이어지는 점까지의 도형을 단순하게 시계 방향으로 돌리면 (0,-2) ~ (-2, -2)로 움직이는 지점과 똑같음을 볼 수 있습니다!

즉, 우상좌상으로 이어지는 선분 각각을 시계 방향으로 90도를 돌리면, 우 -> 하, 상 -> 우, 좌 ->상, 상-> 우가 되죠.

즉, 하우상우가 됩니다.

그렇다면, 끝 점인 (-2,-2)에서 하우상우를 하면 2세대 드래곤 커브의 끝점인 (0,-2)로 이동할 수 있다는 것 입니다.

그럼 여기서 3세대 드래곤을 그리는 방법은 무엇일까요?

하우상우를 뒤에서부터 180도 반대로 그리면 됩니다!

결국, 시계 방향으로 90도 돌린 뒤에 180도를 또 돌리므로, 총 270도를 돌리는 것입니다.

 즉, 우상좌상을 뒤에서부터 반시계 방향으로 90도 돌려서 그리면 된다는 말이죠!!!

우상좌상 -> 상좌상우 -> 좌하좌상 이 되는 것이죠!

처음부터 끝까지 그리는 방법은

'우상좌상좌하좌상'이 되는 것입니다!

이 정보를 또 다시 배열에 저장해서 다음 세대 드래곤을 그릴때 이용하면 됩니다!

const int dr[4] = { 0,-1,0,1 };
const int dc[4] = { 1,0,-1,0 };
const int inv[4] = { 1,2,3,0 };    
 
cod dragon[20];
int direct[20][1024];
int sede[20];
int n;
 
void makeDragon(int nD, int sede)
{
    int nowLength = 1;
    for (int i = 0; i < sede; i++)
    {
        for (int j = nowLength - 1; j >= 0; j--)
        {
            int dir = inv[direct[nD][j]];
            direct[nD][nowLength++] = dir;
            dragon[nD].r += dr[dir];
            dragon[nD].c += dc[dir];
            map[dragon[nD].r][dragon[nD].c] = 1;
        }
    }
}

그렇다면, 이제 4개의 꼭짓점이 모두 드래곤 커브의 일부인지 확인하는 법에 대해서 생각해 봅시다.

우선 맵의 크기는 (0,0) ~ (100,100) 까지 존재합니다.

어짜피 좌표가 101*101개 까지이므로, 충분히 2차원 배열로 표현할 수 있는 범위입니다.

단순하게, 드래곤 커브에서 (x,y)의 점을 그리면, 맵에 1로 체크한 뒤에,

(0,0) ~ (100,100)까지 현재 자신의 좌표 (x,y)와 (x,y+1), (x+1,y), (x+1,y+1)이 모두 1 인지 확인해서 결과값에 더해주면 정답을 구할 수 있습니다!

    const int checkR[4] = { 0,0,1,1 };
    const int checkC[4] = { 0,1,0,1 };
 
    int getSagack()
    {
        for (int i = 0; i < n; i++)
        {
            makeDragon(i, sede[i]);
        }
 
        int res = 0;
        for (int i = 0; i < 100; i++)
        {
            for (int j = 0; j < 100; j++)
            {
                int cnt = 0;
                for (int d = 0; d < 4; d++)
                {
                    cnt += map[i + checkR[d]][j + checkC[d]];
                }
                res += cnt >> 2;
            }
        }
        return res;
    }

코드

#include<iostream>
#include<cstring>
 
using namespace std;
 
struct DragonCurveInfo
{
    int map[101][101];
 
    typedef struct Cod { int r, c; } cod;
 
    const int dr[4] = { 0,-1,0,1 };
    const int dc[4] = { 1,0,-1,0 };
    const int inv[4] = { 1,2,3,0 };
    const int checkR[4] = { 0,0,1,1 };
    const int checkC[4] = { 0,1,0,1 };
    cod dragon[20];
    int direct[20][1024];
    int sede[20];
    int n;
 
    int getSagack()
    {
        for (int i = 0; i < n; i++)
        {
            makeDragon(i, sede[i]);
        }
 
        int res = 0;
        for (int i = 0; i < 100; i++)
        {
            for (int j = 0; j < 100; j++)
            {
                int cnt = 0;
                for (int d = 0; d < 4; d++)
                {
                    cnt += map[i + checkR[d]][j + checkC[d]];
                }
                res += cnt >> 2;
            }
        }
        return res;
    }
 
    void makeDragon(int nD, int sede)
    {
        int nowLength = 1;
        for (int i = 0; i < sede; i++)
        {
            for (int j = nowLength - 1; j >= 0; j--)
            {
                int dir = inv[direct[nD][j]];
                direct[nD][nowLength++] = dir;
                dragon[nD].r += dr[dir];
                dragon[nD].c += dc[dir];
 
                map[dragon[nD].r][dragon[nD].c] = 1;
            }
        }
    }
 
 
 
    void init()
    {
        cin >> n;
        memset(map, 0, sizeof(map));
        for (int i = 0; i < n; i++)
        {
            cin >> dragon[i].c >> dragon[i].r >> direct[i][0] >> sede[i];
            map[dragon[i].r][dragon[i].c] = 1;
 
            dragon[i].r += dr[direct[i][0]];
            dragon[i].c += dc[direct[i][0]];
 
            map[dragon[i].r][dragon[i].c] = 1;
        }
 
    }
}DragonInfo;
 
int main()
{
    DragonInfo.init();
    int res = DragonInfo.getSagack();
    cout << res << '\n';
    return 0;
}

시간 복잡도

드래곤의 세대의 수가 많아질수록 시간복잡도가 커지기 떄문에

가장 세대가 많은 드래곤의 세대 수를 maxn이라고 했을때, 입니다.