백준 12100 2048 (Easy) (C++)

12100번: 2048 (Easy)

2048을 구현하는 문제이다. 우선 상하좌우를 구현해주었다. 현재 위치 다음 값이 0일 경우 다음으로 이동시켜주고, 현재 위치와 같은 값이면 두 값을 합쳐주고 현재 위치를 0으로 바꿔준다. 여기서 주의할 점은 한번의 이동 내에서 한번 합쳐진 경우 두번은 합쳐지면 안되는 것이다. 그래서 check를 통해 이를 확인해준다. check 값 또한 이동시 같이 이동시켜준다. 이를 dfs를 통해 백트래킹을 하면서 모든 경우를 돌면서 최댓값을 찾아 출력해주었다.
굉장히 시간이 오래 걸렸다. 처음에는 2045을 잘못 이해하고 있었다. 2 2 2인 경우 왼쪽으로 이동하면 4 2 0이 되어야 하는데 2 4 0이 되도록 구현했었다. 두번째는 첫번재 문제를 고치는 과정에 반복문 범위를 잘못 입력하였고 이를 몰라 문제를 다른 곳에서 찾느라 시간 낭비가 심했다. 구현 문제 자체가 시간이 오래 걸리고 오타가 많을 수 있기때문에 충분히 주의해야겠다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N, res = 0;
int A[20][20];

void up(int a[][20]) {
    bool check[20][20];

    memset(check, false, sizeof(check));

    for (int j = 0; j < N; j++) {
        while (1) {
            bool tf = false;

            for (int i = 1; i < N; i++) {
                if (a[i][j] == 0) continue;

                if (a[i - 1][j] == 0) {
                    a[i - 1][j] = a[i][j];
                    a[i][j] = 0;
                    tf = true;

                    if (check[i][j]) {
                        check[i - 1][j] = true;
                        check[i][j] = false;
                    }
                }
                else if (a[i - 1][j] == a[i][j] && !check[i - 1][j] && !check[i][j]) {
                    a[i - 1][j] += a[i][j];
                    a[i][j] = 0;
                    tf = true;
                    check[i - 1][j] = true;
                }
            }

            if (!tf) break;
        }
    }
}

void down(int a[][20]) {
    bool check[20][20];

    memset(check, false, sizeof(check));

    for (int j = 0; j < N; j++) {
        while (1) {
            bool tf = false;

            for (int i = N-2; i >= 0; i--) {
                if (a[i][j] == 0) continue;

                if (a[i + 1][j] == 0) {
                    a[i + 1][j] = a[i][j];
                    a[i][j] = 0;
                    tf = true;

                    if (check[i][j]) {
                        check[i + 1][j] = true;
                        check[i][j] = false;
                    }
                }
                else if (a[i + 1][j] == a[i][j] && !check[i+1][j] && !check[i][j]) {
                    a[i + 1][j] += a[i][j];
                    a[i][j] = 0;
                    tf = true;
                    check[i + 1][j] = true;
                }
            }

            if (!tf) break;
        }
    }
}

void left(int a[][20]) {
    bool check[20][20];

    memset(check, false, sizeof(check));

    for (int i = 0; i < N; i++) {
        while (1) {
            bool tf = false;

            for (int j = 1; j < N; j++) {
                if (a[i][j] == 0) continue;

                if (a[i][j - 1] == 0) {
                    a[i][j - 1] = a[i][j];
                    a[i][j] = 0;
                    tf = true;

                    if (check[i][j]) {
                        check[i][j - 1] = true;
                        check[i][j] = false;
                    }
                }
                else if (a[i][j - 1] == a[i][j] && !check[i][j-1] && !check[i][j]) {
                    a[i][j - 1] += a[i][j];
                    a[i][j] = 0;
                    tf = true;
                    check[i][j - 1] = true;
                }
            }

            if (!tf) break;
        }
    }
}

void right(int a[][20]) {
    bool check[20][20];

    memset(check, false, sizeof(check));

    for (int i = 0; i < N; i++) {
        while (1) {
            bool tf = false;

            for (int j = N-2; j >= 0; j--) {
                if (a[i][j] == 0) continue;

                if (a[i][j + 1] == 0) {
                    a[i][j + 1] = a[i][j];
                    a[i][j] = 0;
                    tf = true;

                    if (check[i][j]) {
                        check[i][j + 1] = true;
                        check[i][j] = false;
                    }
                }
                else if (a[i][j + 1] == a[i][j] && !check[i][j+1] && !check[i][j]) {
                    a[i][j + 1] += a[i][j];
                    a[i][j] = 0;
                    tf = true;
                    check[i][j + 1] = true;
                }
            }

            if (!tf) break;
        }
    }
}

void dfs(int depth, int a[][20]) {
    if (depth == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = max(res, a[i][j]);
            }
        }

        return;
    }
    int tmp[20][20];

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

    for (int i = 0; i < 4; i++) {
        switch (i) {
        case 0:
            up(a);
            break;
        case 1:
            down(a);
            break;
        case 2:
            left(a);
            break;
        case 3:
            right(a);
            break;
        }

        dfs(depth + 1, a);

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

void solution() {
    dfs(0, A);

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

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

    solution();

    return 0;
}