🔍 12100 2048 (easy)

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

---

🤔 풀이

• (다 푸는데 2시간 넘게 걸린듯 풀면서 눈물이 났뻔했다... 원래 풀던 방식이 안 돼서 결국 싹 다 엎고 노트에 적어가며 차근차근 다시 설계...)

• 우선 몇 번 이동 이런거 없이 한 번 이동할 때 제대로 되는지부터 확인해야 했다. 내가 생각한 방법은
  1. 방향대로 싹 밀어서 한 군데로 모은다. (순서를 지키며)
  2. 밀어서 모은 숫자들을 확인해 합쳐지는 조건에 맞는 숫자들을 처리한다.
  3. 위에서 처리한 숫자들을 다시 보드에 채운다.
  이다. 해당 방법대로 어떻게 구현할지 밑에서 다시 설명해본다.

1. 방향대로 싹 밀기.
   • 말 그대로 냅다 밀어서 save에 넣는다. 다만, 0이 채워져 있을 경우에는 포함하지 않는다.
     
2. 숫자 합치기
   • 조건을 확인하여 숫자를 합친다. 여기서 한 번 합쳐진 숫자는 다시 다른 숫자와 합쳐지지 않으므로 주의해야 한다. 나는 마치 스택 구조처럼 꺼내 합칠 수 있는지 확인했다. save에서 숫자를 하나씩 꺼낸다. 이 숫자를 꺼낼 때, pre_num과 비교한다.(다만 pre_num은 이전에 한 번 합쳐진 숫자가 들어가지 않게 한다.) 이는 바로 앞에 있던 숫자로, 만약 (방금 꺼낸)나와 값이 똑같지 않다면, 무시하고 그냥 새로운 list에 꺼낸 값을 넣는다. 그리고 pre_num은 방금 넣은 값이 된다. 하지만 만약 똑같다면 두 숫자는 합쳐져 새로운 list에 들어가게 된다. 그리고 pre_num을 -1로 만들어 주어야 한다. 그렇지 않으면 이후 똑같은 숫자와 합쳐지게 되는 꼴이 될 수 있기 때문이다. 이를 save의 모든 값을 확인할 때까지 반복한다.
     
3. 마지막으로 합친 숫자들을 다시 보드에 적는다.
   - 밀어진 방향을 시작으로 다시 숫자들을 채운다. 만약 채울 숫자가 없으면 0으로 채운다.
   
   (나는 방향 순서대로 채운다고 4가지 케이스로 나누었는데 회전을 사용하신 분도 계셨다... 나는 언제쯤 그런 센스를 갖게 될까...)

• 각각 이동이 잘 되는걸 확인했으므로, 5번 이동할 수 있는 경우의 수를 처리하기 위해 해당 과정을 백트래킹으로 진행한다. (여기서 바뀌는 보드를 체크하기 위해 copy 함수를 썼는데, temp_board를 밖으로 빼내서 거기서 계산해도 됐을 것 같다.)

---

📝 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, maxx = 0;
int board[20][20];

vector<int> save[20];
vector<int> list[20];
int dx[2] = { 0, 1 }; // 위, 왼, 아래, 오
int dy[2] = { 1, 0 };


void initialVector() {
    for (int i = 0; i < N; i++) {
        save[i].clear();
        list[i].clear();
    }
}

void reposition(int direction) {    // 3.
    int x, y;

    if (direction == 0) {
        for (int i = 0; i < N; i++) { // dir 0
            for (int j = 0; j < N; j++) {
                if (list[j].size() > i) {
                    board[i][j] = list[j][i];
                    if (maxx < board[i][j]) maxx = board[i][j];
                }
                else {
                    board[i][j] = 0;
                }
            }
        }
    }
    else if (direction == 1) {
        for (int i = 0; i < N; i++) { // dir 1
            for (int j = 0; j < N; j++) {
                if (list[i].size() > j) {
                    board[i][j] = list[i][j];
                    if (maxx < board[i][j]) maxx = board[i][j];
                }
                else {
                    board[i][j] = 0;
                }
            }
        }
    }
    else if (direction == 2) {
        for (int i = N-1; i >= 0; i--) { // dir 2
            for (int j = N-1; j >= 0; j--) {
                if (list[j].size() > (N-i-1)) {
                    board[i][j] = list[j][N-i-1];
                    if (maxx < board[i][j]) maxx = board[i][j];
                }
                else {
                    board[i][j] = 0;
                }
            }
        }
    }
    else if (direction == 3) {
        for (int i = N-1; i >= 0; i--) { // dir 3
            for (int j = N-1; j >= 0; j--) {
                if (list[i].size() > (N-j-1)) {
                    board[i][j] = list[i][N-j-1];
                    if (maxx < board[i][j]) maxx = board[i][j];
                }
                else {
                    board[i][j] = 0;
                }
            }
        }
    }

}

void merge() {  // 2.
    for (int i = 0; i < N; i++) {
        int pre_num = -1;
        int top_idx = 0;
        while (top_idx < save[i].size()) {
            if (save[i][top_idx] == pre_num) {
                pre_num = -1;
                list[i].pop_back();
                list[i].push_back(save[i][top_idx++]*2);
            }
            else {
                pre_num = save[i][top_idx++];
                list[i].push_back(pre_num);
            }
        }
    }
}

void push(int direction) { // 1.
    int x, y;
    if (direction/2 == 0) {
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (board[x][y] != 0) save[x*dx[direction%2] + y*dy[direction%2]].push_back(board[x][y]);
            }
        }
    }
    else {
        for (int x = N-1; x >= 0; x--) {
            for (int y = N-1; y >= 0; y--) {
                if (board[x][y] != 0) save[x*dx[direction%2] + y*dy[direction%2]].push_back(board[x][y]);
            }
        }
    }
}

void find_max() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (maxx < board[i][j]) maxx = board[i][j];
        }
    }
}

void bt(int step) {
    if (step == 5) {
        return ;
    }

    int temp_board[20][20];
    copy(&board[0][0], &board[0][0]+400, &temp_board[0][0]);
    for (int i = 0; i < 4; i++) {
        initialVector();
        copy(&temp_board[0][0], &temp_board[0][0]+400, &board[0][0]);
        push(i);
        merge();
        reposition(i);
        bt(step+1);
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    bt(0);

    cout << maxx;
    return 0;
}