[ SWEA 6109 ] 추억의 2048 게임 (C++)

SWExpertAcademy의 추억의 2048게임(6109 / D4) 문제이다.

[ 문제풀이 ]

1) 문제의 입력으로 주어진 해당 명령어에 맞게 주어진 맵을 움직여 주면 되는 문제이다.

   문제에서는 '상하좌우' 4방향 중 하나의 명령어가 떨어지겠지만, 이 글에서는 이 4방향에 대해서 모두 설명을 하면

   길이 굉장히 길어질 것 같으므로, 본인이 사용한 방식으로 'Left'(좌) 로 움직이는 과정만 설명하겠다.

2) 아래와 같은 예시로 알아보자.

어차피, 왼쪽 방향으로 맵을 기울였을 때만 설명을 할 것이기 때문에, 맵에서 한줄만 가져왔다고 생각하자.

결과부터 말하자면 위의 맵을 왼쪽으로 기울이게 되면 다음과 같아진다.

파랑색 '2', 2개가 합쳐져서 파랑색 '4'로, 빨강색 '2' 2개가 합쳐져서 빨강색 '4'로, 초록색'4'가 옆으로 움직여져서

위의 그림과 같이 위치하게 된다.

본인은 먼저 Vector를 하나 만들어 주었다. 이 Vector에는 지금부터 "0이 아닌 값들을 순차적으로 저장" 할 것이다.

그리고 맵을 탐색하면서 '0'이 아닌 좌표를 찾아보자. 맵 전체를 탐색해야 하므로 탐색 범위는 0 ~ N - 1 이다.

가장 처음에 파랑색 '2'가 나올 것이다. 그럼 우리가 현재 발견한 값은 '2'이다.

그럼 지금부터, 맵의 끝이 나올때 까지 다음과 같은 조건을 확인하면서 반복을 할 것이다. 물론, 중간에 종료될 수도 있다.

1) 현재 발견한 값과 동일한 값이 나온다면, 해당 값의 2배를 해준 값을 벡터에 넣어준다.

   그리고, '동일한 값이 존재했던 Index의 값'을 0으로 바꿔준 후, 반복을 종료한다.

2) 만약, 0이 아닌 값 중, 현재 발견한 값과 다른 값이 나온다면, 현재 발견한 값만 벡터에 넣어주고,

   반복을 종료한다.

3) 1), 2) 모두 해당 사항이 없다면, 그 다음 Index로 넘어간다.

위의 말을 그림으로 알아보자.

가장 처음 '2'를 발견하게 되면, '2'가 있는 Index + 1 부터 탐색을 진행할 것이다. 지금부터 주황색 화살표가 탐색을 할 것이다.

그럼 위의 그림에서 탐색 화살표가 가르키고 있는 '0'은 위의 2가지 조건중에 어디에 해당될까 ? 바로 '3번'에 해당한다.

1번 조건도 아니고, 2번 조건도 만족하지 않기 때문에 3번에 해당한다. 그럼 그 다음 Index로 넘어가보자.

위의 상황은 조건 몇번에 해당될까?? 1번 조건에 해당한다. 현재 발견한 값과 동일한 값을 발견했기 때문이다.

1) 현재 발견한 값과 동일한 값이 나온다면, 해당 값의 2배를 해준 값을 벡터에 넣어준다.

   그리고, '동일한 값이 존재했던 Index의 값'을 0으로 바꿔준 후, 반복을 종료한다.

그렇다면 위의 말대로 해보자. 현재 벡터에는 V = [ ] . 아무런 값도 존재하지 않는다.

이 벡터에, 2배를 해준 값을 넣어준다. 즉 V = [ 4 ] 가 될 것이다.

그리고, '동일한 값이 존재했던 Index의 값'을 0으로 바꿔주고 반복을 종료한다. 그러면 다음과 같이 될 것이다.

이제 반복문을 종료해주자.

그 이후, 맵 탐색을 진행하게 되면, 빨강색 '2'에서 한번 더 위에서 말한 반복을 진행하게 될 것이다.

구체적인 진행과정은 위와 똑같으니 생략하고 결과만 알아보자. 아마 다음과 같이 존재할 것이다.

맵은 이렇게 될 것이고, V = [ 4 , 4 ] 가 될 것이다. (빨강색 '2'를 2배를 해준 값을 벡터에 넣어줬으므로 !)

그리고 마지막 탐색에서는 초록색 '4'에서는 합쳐질 값이 없으므로 아무런 변화도 없을 것이다.

이제, 우리가 만들어 놓은 벡터를 사용할 때이다.

벡터에 있는 값들이 순차적으로 맵의 앞에서부터 들어갈 값들이다.

아까 결과를 봤듯이, 맵의 가장 앞에 '4 4 4' 가 들어가게 된다. 우리가 만들고 저장한 벡터에도 [ 4 4 ] 가 존재한다.

그런데 ! '4'의 갯수가 한 개 부족하다. 왜 부족한지 보면, 가장 마지막 초록색 '4'가 벡터에는 들어가지 않았다.

이런 경우를 위해서, 위에서는 말하지 않았지만, 아무런 변화가 없을 때에도, 해당 값을 넣어줘야 한다.

for (int j = 0; j < N; j++)
{
    if (MAP[i][j] == 0) continue;
    
    int k = j + 1;
    bool Flag = false;
    while (k < N)
    {
        if (MAP[i][j] == MAP[i][k])
        {
            V[i].push_back(MAP[i][j] * 2);
            MAP[i][k] = 0;
            Flag = true;
            break;                        
        }
        if (MAP[i][k] != 0 && MAP[i][j] != MAP[i][k])
        {
            V[i].push_back(MAP[i][j]);
            Flag = true;
            break;
        }
        k++;
    }
    if (Flag == false) V[i].push_back(MAP[i][j]);
}

위의 코드가 왼쪽으로 옮기는 맵을 기울일 때의 코드이다. 라인별로 구체적인 동작 과정을 알아보자.

line 5)

- '0이 아닌 값을 찾았을 때' 탐색을 위한 변수 선언이다. 현재 0이 아닌값을 가르키는 index는 'j'이고, k는 j + 1부터 시작한다.

line 6)

- 밑에서 구체적으로 설명하겠다.

line 7 ~ 23)

- 위에서 말했던 '반복 과정' 이다.

  line 9 ~ 13) 에서 '동일한 값을 찾았을 때', 해당 값의 2배한 값을 벡터에 넣어주고, 해당 Index의 값을 0으로 바꿔준다.

  line 16 ~ 21) 에서 '동일한 값을 찾지 못했을 때'는 해당 값만 벡터에 넣어준다.

line 24)

- 이 부분이 없다면, 우리가 위에서 했듯이, 마지막 초록색 '4'가 Vector에 들어가지질 않는다.

  line 7 ~ 23)에서 봤듯이, 각 조건문에서 Vector에 값이 들어가게 되면, Flag 로 "값이 들어갔습니다" 라고 체크를 해준다.

  하지만, 초록색 '4'처럼, 아무런 변화도 없이 끝나버린다면 ? 해당 '4'만 남는다는 것을 의미한다.

  따라서, 이 경우 그 값도 Vector에 넣어준다.

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < V[i].size(); j++) MAP[i][j] = V[i][j];
    for (int j = V[i].size(); j < N; j++) MAP[i][j] = 0;
}

이 부분은, 우리가 만든 Vector를 이용해서, 맵의 값들을 다시 재설정 해주는 부분이다.

사실, 처음에는 맵에서 인덱스를 계속 찾고, 0으로 바꿔주고, 이러한 과정들이 조금 복잡해서 간편한 방법을 찾다가 본인은

위와 같은 방법을 사용했는데.. 지금 적어보니까 오히려 더 복잡해 진 것 같긴하다.

문제 자체가 시뮬레이션이고 특정 알고리즘이나 자료구조를 사용하는 것이 아니기 때문에 개인이 가장 생각하기 쉬운 방법을

이용해서 해결하는 것이 가장 좋은 것 같다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<string>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N;
int MAP[MAX][MAX];
string Cmd;
 
void Initialize()
{
 
}
 
void Input()
{
    cin >> N >> Cmd;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Print()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
}
 
void Move_Up()
{
    vector<int> V[MAX];
    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < N; i++)
        {
            if (MAP[i][j] == 0) continue;
 
            int k = i + 1;
            bool Flag = false;
            while (k < N)
            {
                if (MAP[i][j] == MAP[k][j])
                {
                    V[j].push_back(MAP[i][j] * 2);
                    MAP[k][j] = 0;
                    Flag = true;
                    break;
                }
 
                if (MAP[k][j] != 0 && MAP[i][j] != MAP[k][j])
                {
                    V[j].push_back(MAP[i][j]);
                    Flag = true;
                    break;
                }
                k++;
            }
            if (Flag == false) V[j].push_back(MAP[i][j]);
        }
    }
 
    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < V[j].size(); i++) MAP[i][j] = V[j][i];
        for (int i = V[j].size(); i < N; i++) MAP[i][j] = 0;    
    }
}
 
void Move_Down()
{
    vector<int> V[MAX];
    for (int j = 0; j < N; j++)
    {
        for (int i = N - 1; i >= 0; i--)
        {
            if (MAP[i][j] == 0) continue;
 
            int k = i - 1;
            bool Flag = false;
            while (k >= 0)
            {
                if (MAP[i][j] == MAP[k][j])
                {
                    V[j].push_back(MAP[i][j] * 2);
                    MAP[k][j] = 0;
                    Flag = true;
                    break;
                }
 
                if (MAP[k][j] != 0 && MAP[i][j] != MAP[k][j])
                {
                    V[j].push_back(MAP[i][j]);
                    Flag = true;
                    break;
                }
                k--;
            }
 
            if (Flag == false) V[j].push_back(MAP[i][j]);
        }
    }
 
    for (int j = 0; j < N; j++)
    {
        for (int i = 0; i < V[j].size(); i++) MAP[N - 1 - i][j] = V[j][i];
        for (int i = V[j].size(); i < N; i++) MAP[N - 1 - i][j] = 0;
    }
}
 
void Move_Left()
{
    vector<int> V[MAX];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 0) continue;
            
            int k = j + 1;
            bool Flag = false;
            while (k < N)
            {
                if (MAP[i][j] == MAP[i][k])
                {
                    V[i].push_back(MAP[i][j] * 2);
                    MAP[i][k] = 0;
                    Flag = true;
                    break;                        
                }
 
                if (MAP[i][k] != 0 && MAP[i][j] != MAP[i][k])
                {
                    V[i].push_back(MAP[i][j]);
                    Flag = true;
                    break;
                }
                k++;
            }
            if (Flag == false) V[i].push_back(MAP[i][j]);
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < V[i].size(); j++) MAP[i][j] = V[i][j];
        for (int j = V[i].size(); j < N; j++) MAP[i][j] = 0;
    }
}
 
void Move_Right()
{
    vector<int> V[MAX];
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j >= 0; j--)
        {
            if (MAP[i][j] == 0) continue;
 
            int k = j - 1;
            bool Flag = false;
            while (k >= 0)
            {
                if (MAP[i][j] == MAP[i][k])
                {
                    V[i].push_back(MAP[i][j] * 2);
                    MAP[i][k] = 0;
                    Flag = true;
                    break;
                }
 
                if(MAP[i][k] != 0 && MAP[i][j] != MAP[i][k])
                {
                    V[i].push_back(MAP[i][j]);
                    Flag = true;
                    break;
                }
                k--;
            }
            if (Flag == false) V[i].push_back(MAP[i][j]);
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < V[i].size(); j++) MAP[i][N - 1 - j] = V[i][j];
        for (int j = V[i].size(); j < N; j++) MAP[i][N - 1 - j] = 0;
    }
}
 
void Solution()
{
    if (Cmd == "up") Move_Up();
    else if (Cmd == "down") Move_Down();
    else if (Cmd == "left") Move_Left();
    else if (Cmd == "right") Move_Right();
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << endl;
        Print();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}