[ SWEA 4112 ] 이상한 피라미드 탐험 (C++)

SWExpertAcademy의 이상한 피라미드 탐험(4112 / D5) 문제이다.

[ 문제풀이 ]

문제를 보고, 주어진 맵을 어떻게 만들어야 할지 정말 고민을 많이 했었던 문제인 것 같다.

맵만 어떻게 만든다면, 그 이후에는 너비우선탐색(BFS)을 통해서 보물을 찾을 때 까지 걸리는 최소시간을

구할 수 있을 거라 생각했다.

그럼 지금부터 맵 만드는 과정을 알아보자.

간단하게 이 15개의 숫자로 한번 알아보도록 하자.

( 지금부터 하는 이야기가 글로만 읽을 때는 이해가 잘 안될 수도 있습니다. 읽어보시고, 소스코드를 참고하시면

  무슨 이야기였는지 이해가 될 겁니다 ! )

먼저, '연결되어 있는 숫자' 를 정할 때, 본인은 무조건 '현재 숫자보다 더 낮은 숫자들이랑만 연결' 을 진행해주었다.

예를 들면, 가장 처음 숫자는 '1'인데, '1'은 그 어떤 숫자와도 연결시켜주지 않는다.

그 다음 숫자인 '2'로 넘어오게 되면, '2'와 '1'을 연결시켜주고, 동시에 '1'과 '2'도 연결되었다고 표시해 주었다.

'3'을 보게 되면, '2'와, '1'과 연결되었다고 표시해주고, 동시에, '1'과 '2'에서도 '3'과 연결되었다고 표시해 주었다.

본인은 숫자를 3가지 종류로 나눠보았다.

1. 가장 왼쪽에 있는 숫자인지

2. 가장 오른쪽에 있는 숫자인지

3. 그게 아닌 숫자인지

먼저, 1번 부류의 숫자들인, 가장 왼쪽에 있는 숫자를 한번 봐보도록 하자. 숫자를 한번 나열해보면 다음과 같아진다.

[ 1 , 2 , 4 , 7 , 11 ... ]

이런식으로 숫자가 존재한다. 그럼 규칙을 한번 찾아보자.

1 → 2 로 갈 때 + 1

2 → 4 로 갈 때 + 2

4 → 7 로 갈 때 + 3

7 → 11 로 갈 때 + 4

아마 그 다음 층의 가장 왼쪽 숫자는 11 → x 로 갈 때, + 5 가 되어서 x = 16이 될 것이다.

대충 눈치챘겠지만, 가장 왼쪽의 숫자들은, + 1, + 2, + 3, + 4 , + 5... 이런 식으로 증가하는 규칙이 존재한다.

그럼, 언제 + 1을 하고 언제 + 2를 하고 언제 + 3을 해야할까?? 바로 저 숫자들은 '층수'를 의미한다.

'1'을 1층이라고 가정하고, '2, 3' 을 2층, '4 5 6' 을 3층 이라고 생각해보자.

1층에서 가장 왼쪽에 있는 숫자인 '1'을 연결을 진행했다면, 그 다음 층의 가장 왼쪽에 있는 숫자는 '1'에서 '1층'을 더한

'2'가 되는 것이다.

2층에서 가장 왼쪾에 있는 숫자인 '2'를 연결을 진행했다면, 그 다음 층의 가장 왼쪽에 있는 숫자는 '2'에서 '2층'을 더한

'4'가 되는 것이다.

이정도 규칙이 있다는 것만 파악하고 보다 구체적인건 밑에서 계속 알아보도록 하자.

그럼 ! 이제 이 숫자들은 어떤 숫자들과 연결되는지 한번 알아보자.

위에서도 말했듯이, 더 작은 숫자들이랑만 연결을 할 것이다 !!!!

'2'를 한번 봐보자. '2'는 가장 왼쪽에 있는 숫자이다. 그리고 '1'과 연결되어 있다. (3은 더 큰 숫자이므로 pass)

그 다음 숫자인 '4'를 한번 봐보자. '4'는, '2'와 연결되어 있다.

즉 ! "더 작은 숫자들이랑만 연결을 진행했을 때, 가장 왼쪽에 있는 숫자들은, 한 단계 아랫층의 가장 왼쪽에 있는

숫자와 연결" 이 된다.

그럼, 우리는 가장 왼쪽에 있는 숫자가 "어떤 숫자들이 가장 왼쪽에 오게 되는지, 어떤 숫자들과 연결되는지" 까지

다 알았다. 그럼 필요한 값들을 이야기를 해보자.

1. 현재 층수 : 현재 숫자로 부터, 그 다음 층의 가장 왼쪽에 오는 숫자의 값을 알기 위해서 필요한 값이다.

               현재 숫자 + 층수 를 하면 그 다음 층의 가장 왼쪽에 오는 숫자를 알 수 있다.

2. 가장 왼쪽에 있는 숫자 : 현재 숫자와 , 현재 층수를 이용해서 계산할 수 있는 값이다.

3. 한 단계 아랫층의 가장 왼쪽에 있는 숫자 : 현재 숫자가, 가장 왼쪽에 있는 숫자라면, 이 숫자는 한 단계 아랫층의

                                            가장 왼쪽에 있는 숫자랑만 연결이 되므로, 연결을 위해 필요한 값이다.

지금까지 "가장 왼쪽에 있는 숫자" 의 경우를 알아보았다.

그럼, 가장 오른쪽에 있는 숫자를 이제 알아보자.

가장 오른쪽의 숫자들을 보면 [ 1 , 3 , 6 , 10 , 15 ... ] 이런식으로 진행된다.

규칙을 찾아보면...

1 → 3 으로 갈 때, + 2

3 → 6 으로 갈 때, + 3

6 → 10 으로 갈 때, + 4

10 → 15 로 갈 때, + 5

이런 규칙이 있다. '가장 왼쪽에 있는 숫자'를 계산할 때는 '현재 숫자 + 현재 층수' 를 진행하면 그 다음 층의 가장 왼쪽에

있는 숫자가 나왔는데, '가장 오른쪽에 있는 숫자'를 계산할 때는 '현재 숫자 + 현재 층수 + 1'을 하게 되면 그 다음 층의

가장 오른쪽에 있는 숫자를 계산할 수 있다.

1 → 3 으로 가는 경우를 보자.

현재숫자 1 + 현재 층수 1 + 1 = 3

3 → 6 으로 가는 경우를 보자.

현재숫자 3 + 현재 층수 2 + 1 = 6

이런식의 규칙이 존재한다.

그럼, 가장 오른쪽에 있는 숫자들은 어떤 숫자들과 연결이 될까 ? 여기서도 역시, 더 작은 숫자들만 계산할 것이다.

가장 오른쪽에 있는 숫자들은 2개의 숫자와 연결이 된다.

1. 한 단계 아랫층의 가장 오른쪽에 있는 숫자

2. 현재 자신의 숫자 - 1 한 숫자.

별다른 설명이 없어도, 위의 2개의 숫자와 연결된다는 것을 쉽게 알 수 있을거라 생각한다.

마지막으로, 이도저도 아닌, 가장 왼쪽도, 가장 오른쪽도 아닌 숫자들을 한번보자.

그림을 다시한번 가져와 봤는데, 가장 가운데에 있는 '5'를 한번보자. '5'는 가장왼쪽도, 오른쪽도 아닌 숫자이다.

'5'와 연결된 숫자들을 한번 봐보자. (더 작은 값들만 ! )

'5'는, '2'와, '3'과, '4'와 연결이 되어있다. 여기까지만 봐서는 아직 잘 모르겠다, 그럼 밑에 '8'을 봐보자.

'8'은 '4'와, '5'와, '7'과 연결이 되어있다.

'9'까지해보면, '9'는, '5'와 '6'과, '8'과 연결이 되어있다.

연결되어 있는 숫자들은 아래와 같이 3개의 숫자들과 연결이 된다.

1. 현재숫자 - 현재층수 를 한 숫자

2. 현재숫자 - 현재층수 + 1을 한 숫자

3. 현재숫자 - 1을 한 숫자

위의 규칙이 맞는지 한번 보자. '5'를 예로 들어보자.

'5'는 현재 3층에 존재한다.

1. 현재숫자 - 현재층수를 한 숫자 : 5 - 3 = 2

2. 현재숫자 - 현재층수 + 1을 한 숫자 : 5 - 3 + 1 = 3

3. 현재숫자 -1 을 한 숫자 : 5 - 1 = 4

정말로, '2' '3' '4'와 연결이 된다.

'8'로 한번 더해보자.

1. 현재숫자 - 현재층수를 한 숫자 : 8 - 4 = 4

2. 현재숫자 - 현재층수 + 1을 한 숫자 : 8 - 4 + 1 = 5

3. 현재숫자 - 1을 한 숫자 : 8 - 1 = 7

이렇게 3개의 숫자와 연결이 된다.

내용이 생각보다 굉장히 길어졌는데, 이와 같은 규칙들을 찾아서 본인은 연결관계를 만들어 주었다.

void Setting()
{
    /* 변수설명
     * Floor = 현재 층수를 나타내는 변수.
     * Left = 가장 왼쪽에 있는 숫자를 저장하는 변수.
     * Right = 가장 오른쪽에 있는 숫자를 저장하는 변수.
     * Num = 현재 숫자
     * Cnt = 숫자의 갯수 (각 층은, 각 층이 나타내는 숫자만큼의 숫자가 존재한다.)
     *       ex) 1층의 경우 숫자 '1' 1개. 2층의 경우 '2 3' 2개. 3층의 경우 '4 5 6' 3개.
     * Before_Left = 한 단계 아랫층의 가장 왼쪽에 있는 숫자를 저장하는 변수. (연결을 위함)
     * Before_Right = 한 단계 아랫층의 가장 오른쪽에 있는 숫자를 저장하는 변수. (연결을 위함)
     */
 
    /* 시작은 '2층'부터 진행된다. 왜냐하면, '1'은 연결할 숫자가 존재하지 않기 때문이다. 
     * 또한, '1'은 '가장 왼쪽에 있으면서 가장 오른쪽에 있는' 까다로운 녀석이기 때문에 !
     * 따라서, 초기 시작 숫자는 '2'.
     */
    int Floor, Left, Right, Num, Cnt, Before_Left, Before_Right;
    Floor = 2; Left = 2; Right = 3; Num = 2; Cnt = 0;
    Before_Left = Before_Right = 1;
    /* 2층에 맞게 변수들을 설정. */
    /* 층수 : 2층 , 왼쪽에 있는 숫자 = 2 , 오른쪽에 있는 숫자 = 3 , 현재숫자 = 2 */
    /* 한 단계 아랫층의 왼쪽 & 오른쪽에 있는 숫자 = 1 로 초기설정.
     */
 
    while (Num < MAX)
    {
        if (Num == Left)
        {
            /* 현재 숫자가 가장 왼쪽에 있는 숫자라면*/
            /* 1. 한 단계 아랫층의 있는 왼쪽 숫자와 연결. 
             * 2. 연결된 한 단계 아랫층의 왼쪽 숫자도 현재 숫자와 연결.
             * 3. 그 다음 층의 왼쪽 숫자를 미리 설정 : 현재숫자 + 현재층수
             * 4. 한 단계 아랫층의 왼쪽 숫자를 현재 숫자로 변경 
             */
            V[Num].push_back(Before_Left);
            V[Before_Left].push_back(Num);
            Before_Left = Left;
            Left = Left + Floor;
        }
        else if (Num == Right)
        {
            /* 현재 숫자가 가장 오른쪽에 있는 숫자라면 */
            /* 1. 한 단계 아랫층의 오른쪽에 있는 숫자와 연결
             * 2. 연결된 한 단계 아랫층의 오른쪽 숫자도 현재 숫자와 연결
             * 3. 현재숫자 - 1 을 한 숫자와 연결.
             * 4. 현재숫자 - 1 을 한 숫자도, 현재 숫자와 연결
             * 5. 그 다음 층의 오른쪽 숫자를 미리 설정 : 현재숫자 + 현재층수 + 1
             * 6. 한 단계 아랫층의 오른쪽 숫자를 현재 숫자로 변경
             */
            V[Num].push_back(Before_Right);
            V[Num].push_back(Num - 1);
            V[Before_Right].push_back(Num);
            V[Num - 1].push_back(Num);
            Before_Right = Right;
            Right = Right + Floor + 1;
        }
        else
        {
            /* 이도 저도 아닌 숫자일 경우 */
            /* 1. 현재 숫자 - 층수 를 한 숫자와 연결.
             * 2. 현재 숫자 - 층수 + 1 을 한 숫자와 연결.
             * 3. 현재 숫자 - 1 을 한 숫자와 연결.
             * 4. 1, 2, 3번의 반대 경우도 연결.
             */
            V[Num].push_back(Num - Floor);
            V[Num].push_back(Num - Floor + 1);
            V[Num - Floor].push_back(Num);
            V[Num - Floor + 1].push_back(Num);
            V[Num].push_back(Num - 1);
            V[Num - 1].push_back(Num);
        }
        Num++;
        Cnt++;
        /* 숫자를 계속 ++ 시켜줌과, 현재 층수에 들어간 숫자의 갯수(Cnt)도 ++ */
        /* 만약, Cnt의 값이 현재 층수와 동일하다면, 이제 그 다음 층으로 넘어감을 의미. */
        if (Cnt == Floor)
        {
            Cnt = 0;
            Floor++;
        }
    }
}

이게 본인이 구현한 초기 맵을 세팅하는 코드이다.

위에서 글로만 읽었을 때, 이해가 잘 가지 않았을 수 있는데 코드를 본다면 이해가 갈 것이다.

맵을 만든 이후에는 BFS탐색으로 최단경로를 찾아주었다.

이 부분은 주의해야할 부분이나 그런 점이 없으므로 별다른 설명을 생략하겠다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 10001
using namespace std;
 
int Start, End, Answer;
vector<int> V[MAX];
bool Visit[MAX];
 
void Setting()
{
    int Floor, Left, Right, Num, Cnt, Before_Left, Before_Right;
    Floor = 2; Left = 2; Right = 3; Num = 2; Cnt = 0;
    Before_Left = Before_Right = 1;
 
    while (Num < MAX)
    {
        if (Num == Left)
        {
            V[Num].push_back(Before_Left);
            V[Before_Left].push_back(Num);
            Before_Left = Left;
            Left = Left + Floor;
        }
        else if (Num == Right)
        {
            V[Num].push_back(Before_Right);
            V[Num].push_back(Num - 1);
            V[Before_Right].push_back(Num);
            V[Num - 1].push_back(Num);
            Before_Right = Right;
            Right = Right + Floor + 1;
        }
        else
        {
            V[Num].push_back(Num - Floor);
            V[Num].push_back(Num - Floor + 1);
            V[Num - Floor].push_back(Num);
            V[Num - Floor + 1].push_back(Num);
            V[Num].push_back(Num - 1);
            V[Num - 1].push_back(Num);
        }
        Num++;
        Cnt++;
 
        if (Cnt == Floor)
        {
            Cnt = 0;
            Floor++;
        }
    }
}
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> Start >> End;
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(Start, 0));
    Visit[Start] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == End)
        {
            Answer = Cnt;
            return;
        }
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i];
            if (Next < MAX && Visit[Next] == false)
            {
                Visit[Next] = true;
                Q.push(make_pair(Next, Cnt + 1));
            }
        }
    }
}
 
void Solve()
{
    Setting();
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}