문제 푼 날짜 : 2021-09-19

문제

문제 링크 : https://www.acmicpc.net/problem/12100

접근 및 풀이

스도쿠와 더불어 2048도 아주 유명한 게임이기 때문에 규칙에 대해서 이해하는데 어렵진 않았다.
백트래킹을 어떤 매개변수로 해서 설계해야하는지 보다는 상, 하, 좌, 우로 블록들을 이동시켰을 때 블록들이 합쳐지는 것을 처리하는 게 좀 더 까다로웠던 것 같다.
최대 다섯번 움직일 수 있다고 했기 때문에 이를 움직이는 횟수를 매개변수로 하여 구현하였다.

블록을 움직이고 합치는 부분은 아래의 생각대로 구현하였다.

1. 블록을 하나씩 움직이는 방향으로 최대한 당겨준다.
2. 움직여진 곳에서 인접해있는 블록과 합쳐질 수 있는지 확인해준다.
   2-1. 이 때, 이동을 통해 합쳐진 블록은 한 번 더 합쳐질 수 없으므로, 이 것을 체크해주면서 합쳐준다.

코드

// 백준 12100번 : 2048 (Easy)
#include <iostream>

using namespace std;

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

int N;
int Board[21][21];
int maxNum = -1;

void combine(int move) {
    if (move == UP) {
        bool check[21][21] = { false };
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int tmp = j;
                while (true) {
                    if (tmp <= 0 || Board[tmp - 1][i] != 0) {
                        break;
                    }
                    Board[tmp - 1][i] = Board[tmp][i];
                    Board[tmp][i] = 0;
                    tmp--;
                }
                if (tmp > 0 && Board[tmp - 1][i] == Board[tmp][i] && !check[tmp - 1][i]) {
                    check[tmp - 1][i] = true;
                    Board[tmp - 1][i] *= 2;
                    Board[tmp][i] = 0;
                }
            }
        }
    } else if (move == RIGHT) {
        bool check[21][21] = { false };
        for (int i = 0; i < N; i++) {
            for (int j = N - 1; j >= 0; j--) {
                int tmp = j;
                while (true) {
                    if (tmp >= N - 1 || Board[i][tmp + 1] != 0) {
                        break;
                    }
                    Board[i][tmp + 1] = Board[i][tmp];
                    Board[i][tmp] = 0;
                    tmp++;
                }
                if (tmp < N - 1 && Board[i][tmp + 1] == Board[i][tmp] && !check[i][tmp + 1]) {
                    check[i][tmp + 1] = true;
                    Board[i][tmp + 1] *= 2;
                    Board[i][tmp] = 0;
                }
            }
        }
    } else if (move == DOWN) {
        bool check[21][21] = { false };
        for (int i = 0; i < N; i++) {
            for (int j = N - 1; j >= 0; j--) {
                int tmp = j;
                while (true) {
                    if (tmp >= N - 1 || Board[tmp + 1][i] != 0) {
                        break;
                    }
                    Board[tmp + 1][i] = Board[tmp][i];
                    Board[tmp][i] = 0;
                    tmp++;
                }
                if (tmp < N - 1 && Board[tmp + 1][i] == Board[tmp][i] && !check[tmp + 1][i]) {
                    check[tmp + 1][i] = true;
                    Board[tmp + 1][i] *= 2;
                    Board[tmp][i] = 0;
                }
            }
        }
    } else if (move == LEFT) {
        bool check[21][21] = { false };
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int tmp = j;
                while (true) {
                    if (tmp <= 0 || Board[i][tmp - 1] != 0) {
                        break;
                    }
                    Board[i][tmp - 1] = Board[i][tmp];
                    Board[i][tmp] = 0;
                    tmp--;
                }

                if (tmp > 0 && Board[i][tmp - 1] == Board[i][tmp] && !check[i][tmp - 1]) {
                    check[i][tmp - 1] = true;
                    Board[i][tmp - 1] *= 2;
                    Board[i][tmp] = 0;
                }
            }
        }
    }
}

void play_2048(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                maxNum = max(maxNum, Board[i][j]);
            }
        }
        return;
    }

    int cBoard[21][21];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cBoard[i][j] = Board[i][j];
        }
    }

    for (int move = 0; move < 4; move++) {
        combine(move);
        play_2048(cnt + 1);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Board[i][j] = cBoard[i][j];
            }
        }
    }
}

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

    cout << maxNum;
    return 0;
}

결과

피드백

이런 문제는 세세한 구현이 핵심이므로 집중해서 실수하지 않도록 구현을 해야겠다.