[백준] 12100번 : 2048 (Easy) - C++

백준 12100번 : 2048 (Easy)

등급 : Gold II

12100번: 2048 (Easy) (acmicpc.net)

12100번: 2048 (Easy)

사용 알고리즘 : Brute-Force, Backtracking

사용 자료구조 : Deque

 

각 블럭의 이동을 모두 직접 구현해주고, 그에 따른 최대값을 도출하는 문제.

( 전치 행렬에 대한 부분에서 헷갈리실 수 있다고 생각이 드는데, 추후에 필요하면 더 업데이트 하도록 하겠습니다 )

---

  1. 전치행렬로 변환시키는 함수 생성.

      (i와 j를 서로 바꾼 행렬을 말한다)

  2. 전치행렬을 바탕으로 Up, Left와 Down, Right 함수를 통합하여 구현 가능.

       1) 바뀔 위치를 임시로 저장해 줄 배열(save_tmp)을 생성.

       2) 한 쪽으로 기울일 때, 앞에 아무것도 없는 경우 (0이 들어간 경우) 기울인 쪽의 가장 앞으로 이동.

           → 0이 아닌 값이 나올 때까지 복제된 행렬(cpy)에서 0을 pop.

       3) 해당 행이 비어있지 않은 경우, 가장 앞자리를 save_tmp에 저장.

       4) 확인하는 줄이 비어있지 않고 사이즈가 2 이상인 경우 이동 연산 진행.

           - 확인하는 줄이 비어있는지 : save_tmp가 비어있는지 확인. → 0이 나올 경우 pop을 했으므로, 0만 존재한다면 save_tmp는 empty.

           - 사이즈가 2 이상인지 : cpy의 사이즈가 1이면 하나의 유의미한 값만 들어 있는 것이므로 연산할 필요가 없음.

       5) 2048의 연산을 시작.

           - 연쇄 작용이 일어나는지 확인. → 하나의 점마다 순차적으로 확인하므로 연쇄 작용이 일어날 수 있음.

              ex) 2 2 4 8 16 → 4 4 8 16 → 8 8 16 → 16 16 →  32. 한 번의 이동이라면 4 4 8 16 0이 나와야 하는데 32 0 0 0 0이 나오게 됨.

             이를 막기 위해 이전에 한 번 합연산이 일어났다면 그 다음에는 바로 일어나지 못하게 적용. (chk)

           - 다음에 오는 값이 빈 칸인 경우(0인 경우) save_tmp에 아무 것도 넣지 않고 넘어감.

           - 위의 과정을 진행하면서 최대값을 갱신.

           - 연산을 모두 마치면, 사이즈에 맞게 나머지 공간을 모두 0으로 채워준다. 위의 경우 32를 32 0 0 0 0으로.

           - 수정된 행을 복제 행렬(cpy)의 행마다 대입해주고, 마지막엔 연산 된 행렬을 return.

  3. 백트래킹 함수로 각각의 경우를 모두 탐색 - Up, Down, Left, Right

       1) 5번 순회하는 경우 중지하도록 구현.

       2) 각 방향으로 이동하는 4가지 탐색을 진행.

           - 원본 행렬을 복제한 후 이동을 수행해 원본 행렬에 대입.

           - Up과 Left, Down과 Right를 합쳐놨는데, 이는 Deque의 앞에서 빼는 경우와 뒤에서 빼는 경우를 구현한 것이다.

           - 일반적인 수행 방법으로 Up과 Down은 해당하는 셀을 pop 할 수 없기 때문에 Transpose를 적용. (마지막에 다시 Transpose로 복원)

       3) 이동을 적용한 행렬을 넣어 순회 횟수를 1 증가시켜 다시 진행.

  4. 메인 함수에서 행렬을 입력받을 때 최대값을 저장시켜두고, 위의 함수들을 바탕으로 탐색 진행.

---

#include <iostream>
#include <deque>

using namespace std;

int n;
int ans = 0;

deque <deque <int>> v;
deque <deque <int>> transpose(deque <deque <int>> d)
// 전치행렬로 변환시키는 함수
{
    deque <deque <int>> tmp(n, deque <int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            tmp[i][j] = d[j][i];
        }
    }
    return tmp;
}

deque <deque <int>> calc_even(deque <deque <int>> cpy)
// 위쪽 또는 왼쪽으로 이동하는 경우 : push_back의 경우
{
    for (int j = 0; j < n; j++)
    {
        deque <int> save_tmp;
        // 바뀔 위치를 임시로 저장해줄 배열
        while (!cpy[j].empty() && cpy[j].front() == 0)
        {
            cpy[j].pop_front();
        }
        // 가장 앞 부분이 비어있는 경우 : 연산 없이 이동
        if(!cpy[j].empty() && cpy[j].front() != 0) save_tmp.push_back(cpy[j].front());
        // 확인하는 줄이 비어있지 않고, 가장 앞이 비어있지 않은 경우 : 가장 앞 자리를 저장

        if (!save_tmp.empty() && cpy[j].size() >= 2)
        // 확인하는 줄이 비어있지 않고 사이즈가 2 이상일 때
        {
            bool chk = false;
            // 연쇄 작용이 일어나지 않도록 하기 위한 bool 변수 : 2 2 4 8 16 → 4 4 8 16 0 으로 되도록
            for (int k = 1; k < cpy[j].size(); k++)
            {
                if (cpy[j][k] == 0) continue;
                // 빈 칸이 있는 경우 넘어감
                if (cpy[j][k] == save_tmp.back() && !chk)
                // 두 수가 같고, 연쇄적이지 않은 경우
                {
                    save_tmp.back() *= 2;
                    // 두 수가 같으므로 앞서 들어간 수에 2배를 해서 다시 저장해준다
                    ans = max(ans, save_tmp.back());
                    // 문제의 목표인 최대값을 구하기 위해 현재 값이 최대값이면 저장
                    chk = true;
                    // 연쇄 반응이 일어날 수 있으므로 방금 결합이 일어났음을 표시
                }
                else
                {
                    save_tmp.push_back(cpy[j][k]);
                    chk = false;
                    // 연쇄 반응 가능성이 없어짐을 표시
                }

            }
        }
        while (save_tmp.size() != n)
        // 임시 배열의 사이즈가 작은 경우 합쳐지거나 빈 공간이 제외된 것이므로 0을 마저 다 채워주도록 한다
        {
            save_tmp.push_back(0);
        }
        cpy[j] = save_tmp;
        // 탐색 한 행렬의 줄을 임시 배열로 바꿔준다
    }
    return cpy;
}

deque <deque <int>> calc_odd(deque <deque <int>> cpy)
// 아래쪽 또는 오른쪽으로 이동하는 경우 : push_front의 경우
{
    for (int j = 0; j < n; j++)
    {
        deque <int> save_tmp;
        while (!cpy[j].empty() && cpy[j].back() == 0)
        {
            cpy[j].pop_back();
        }
        if (!cpy[j].empty() && cpy[j].back() != 0) save_tmp.push_front(cpy[j].back());
        if (!save_tmp.empty() && cpy[j].size() >= 2)
        {
            bool chk = false;
            for (int k = cpy[j].size() - 2; k >= 0; k--)
            {
                if (cpy[j][k] == 0) continue;
                if (cpy[j][k] == save_tmp.front() && !chk)
                {
                    save_tmp.front() *= 2;
                    ans = max(ans, save_tmp.front());
                    chk = true;
                }
                else
                {
                    save_tmp.push_front(cpy[j][k]);
                    chk = false;
                }
            }
        }
        while (save_tmp.size() != n)
        {
            save_tmp.push_front(0);
        }
        cpy[j] = save_tmp;
    }
    return cpy;
}


void dfs(int x, deque <deque <int>> d)
// 탐색 및 백트래킹 함수
{
    if (x == 5) return;
    // 5번 순회하는 경우 중지
    else
    {
        for (int i = 0; i < 4; i++)
        {
            if (i == 0)
            // 왼쪽의 경우
            {
                deque <deque <int>> cpy(d);
                // 원본 행렬을 복사
                cpy = calc_even(cpy);
                // 이동 계산
                dfs(x + 1, cpy);
                // 수행 횟수를 1회 추가하고 이동이 완료된 행렬로 재탐색
            }
            else if (i == 1)
            // 오른쪽의 경우
            {
                deque <deque <int>> cpy(d);
                cpy = calc_odd(cpy);
                dfs(x + 1, cpy);
            }
            else if (i == 2)
            // 위쪽의 경우
            // 세로 방향이므로 행렬을 전치시켜준다
            {
                deque <deque <int>> cpy(transpose(d));
                cpy = calc_even(cpy);
                dfs(x + 1, transpose(cpy));
            }
            else
            // 아래쪽의 경우
            // 세로 방향이므로 행렬을 전치시켜준다
            {
                deque <deque <int>> cpy(transpose(d));
                cpy = calc_odd(cpy);
                dfs(x + 1, transpose(cpy));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    v.resize(n, deque <int>(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> v[i][j];
            ans = max(ans, v[i][j]);
            // 행렬을 입력받으면서 최대값을 갱신시켜준다
        }
    }
    dfs(0, v);
    cout << ans;
}