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

백준의 드래곤커브(15685) 문제이다.

( 문제 바로가기 )

삼성의 SW역량테스트 기출문제이다.

[ 문제풀이 ]

1. 그냥 문제를 보면 무슨소린지도 잘 모르겠고, 드래곤커브가 뭔지도 잘 모르겠다 사실. 대충 간략하게 설명을 해보자면

   일정한 규칙을 가지고 선이 그어진다는 말이다. ( 이부분은 문제를 다시한번 읽고오자 설명하기 힘들다)

2. 솔직히 입력은 뭐 이해를 잘 못하겠고, 문제에서 문제설명으로 주어진 경우를 예를 들어서 설명해보겠다.

   처음 0세대에 진행방향이 오른쪽인 드래곤커브는

   이런 모양이라고 한다. 한 세대가 지나 1세대인 드래곤커브는 저 변이 90도 회전하고 끝점에 추가된 형태이다.

   그려보자면, 이런모양이 된다.

   이런식으로 3세대 까지 진행하면 뭐 대충 이런모양이 된다고 한다.

   진짜 손이 가는대로 그어놓은 것 같지만, 찾아보면 규칙이 존재한다.

   문제에서 주어진 방향정보가 [ 0 = → , 1 = ↑ , 2 = ← , 3 = ↓ ] 이렇게 된다.

   이 정보를 토대로 규칙을 찾아보자면

   0세대 : 0

   1세대 : 0 1

   2세대 : 0 1 2 1

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

  

    줄로 연결한 선들을 잘 봐보자. 규칙을 찾을 수 있을 것이다.

    즉, A세대의 방향정보를 나열했을 때, A+1세대에서 추가되는 선분의 방향정보를 알 수 있다.

    한 세대의 방향정보를 역순으로 탐색하면서 +1 을 시켜준 값이 그 다음 세대의 방향정보라는 것이다.

    하지만, 여기서 주의해야 할 점이 4세대를 생각해봐야 한다.

    위의 그림은 3세대 까지만 계산한 것이고, 4세대를 계산해본다고 해보자. 분명히 3세대에 존재하는 3이라는 방향정보 때문에

    4라는 값이 4세대에는 나오게 될 것인데, 문제에서 주어진 방향정보에는 4가 존재하지 않는다.

    직접 해보면 알겠지만, 사실상 3은 +1이 된 4가 아니라 0이 될 것이다. 이를 토대로 결론을 내려보자면

    다음 세대의 추가되는 선분의 방향정보 = 이전 세대의 방향정보를 역순으로 탐색하면서 + 1 % 4 를 한 것이 된다.

   

식으로 나타내자면 이렇게 될 것이다.

3. 문제의 골칫덩어리는 해결했다. 이제 쉬운일만 남았다.

   이제 위에서 구한 방향 정보를 토대로 직접 드래곤 커브를 그리기만 하면 된다.

   먼저 입력으로는 시작점과, 진행방향 , 몇 세대 까지 진행되는지가 주어진다.

   그럼 일단 시작점을 표시해주자. MAP[x][y] = 1 혹은 MAP[x][y] = true 등 원하는 걸로 !

   그리고 일단 진행방향으로 한 번은 진행해주자. 왜냐하면 0세대가 주어진다고 해도, 선분이 하나는 생기기 때문이다.

   x = x + dx[d] & y = y + dy[d] 진행을 하고, MAP[x][y] = 1 로 또 표시해주자.

   그렇다면 이제 선분이 하나 그어진 것이다. 여기서 신경써줘야 할 것이 방향 정보를 저장해 놔야 한다는 것이다.

   왜냐하면, 이 방향정보는 다음세대의 방향정보를 구할 단서이기 때문이다.

   본인 같은 경우는 Vector를 하나 사용했으며, Vector에 넣어주었다.

   이후, 해야할 일을 정리해보겠다.

   [ 현재까지 해놓은 일 ]

   1. 일단 몇 세대가 입력으로 주어지던 간에 0세대 일 때 선분 하나는 그어놓았다.

   2. 현재 진행방향에 대한 정보를 Vector에 저장해 두었다.

   [ 앞으로 해야할 일 ]

   1. 이전 세대의 진행방향을 저장해둔 Vector를 통해서 다음 세대의 추가되는 선분의 진행방향을 알아낸다.

   2. 1)을 통해 알아낸 진행방향대로 좌표를 진행시키고, 표시를 한다.

   3. 물론, 이 다음 세대를 위해서 지금 알아낸 진행방향 또한 Vector에 저장해둔다.

   4. 모두 다 했다면, 사각형의 갯수를 구한다.

   말로 구구절절 설명하기 힘들어서 간단하게 정리해보았다. 어려운 부분에 대한 설명은 다 했기 때문에 저 순서대로

   구현만 잘 하신다면 문제없이 해결할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int N, x, y, d, g, Sx, Sy;
int MAP[MAX][MAX];
 
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0 ,-1 ,0 };
 
vector<int> Dir_Info;
 
void Input()
{
    cin >> N;
}
 
void Make_Dragon_Curve()
{
    int S = Dir_Info.size();
    for (int i = S - 1; i >= 0; i--)
    {
        int nD = (Dir_Info[i] + 1) % 4;
        x = x + dx[nD];
        y = y + dy[nD];
        MAP[x][y] = 1;
 
        Dir_Info.push_back(nD);
    }
}
 
void Count_Square()
{
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (MAP[i][j] == 1 && MAP[i + 1][j] == 1 &&
                MAP[i][j + 1] == 1 && MAP[i + 1][j + 1] == true)
            {
                Cnt++;
            }
        }
    }
    cout << Cnt << endl;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        cin >> y >> x >> d >> g;
 
        Dir_Info.clear();
 
        MAP[x][y] = 1;
        x = x + dx[d];
        y = y + dy[d];
        MAP[x][y] = 1;
 
        Dir_Info.push_back(d);
        for (int j = 0; j < g; j++)
        {
            Make_Dragon_Curve();
        }
    }
 
    Count_Square();
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}