BOJ)12100 2048 (Easy)

문제:icpc.me/12100

2048 게임에서 가능한 5번의 움직임 이내에 나올 수 있는 가장 큰 블럭을 출력하는 문제이다.

하나의 상태에서 가능한 움직임은 4방향이고 N*N의 모든 블럭이 움직여야 하므로 하나의 상태에서 4방향으로 움직일 때 연산 횟수는 4*N*N이다.

5번 움직일 때 나올 수 있는 모든 횟수는 4^5이므로 모든 경우를 전부 구했을 때 시간 복잡도는 (1024*N^2*4)이므로 완전 탐색으로 해결 가능하다.

이 때 주의해야 할 점은 한번의 움직임에서 이미 합쳐진 블럭은 다시 안합쳐지므로 visited배열을 관리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, x;
vector<vector<int>> vt;
int bfs() {
    queue<vector<vector<int>>> qu;
    qu.push(vt);
    int ret = 0, c = 0;
    while (qu.size()) {
        int qs = qu.size();
        while (qs--) {
            vector<vector<int>> v = qu.front();
            vector<vector<int>> visited(n);
            qu.pop();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    ret = max(ret, v[i][j]);
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> up = v;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int cx = i;
                    while (cx - 1 >= 0 && up[cx - 1][j] == 0)
                        cx--;
                    if (cx - 1 >= 0 && up[cx - 1][j] == up[i][j] && !visited[cx - 1][j]) {
                        up[cx - 1][j] = up[i][j] * 2;
                        up[i][j] = 0;
                        visited[cx - 1][j] = 1;
                    }
                    else 
                        swap(up[cx][j], up[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> down = v;
            for (int i = n - 2; i >= 0; i--) {
                for (int j = 0; j < n; j++) {
                    int cx = i;
                    while (cx + 1 < n&&down[cx + 1][j] == 0)
                        cx++;
                    if (cx + 1 < n&&down[cx + 1][j] == down[i][j] && !visited[cx + 1][j]) {
                        down[cx + 1][j] = down[i][j] * 2;
                        down[i][j] = 0;
                        visited[cx + 1][j] = 1;
                    }
                    else 
                        swap(down[cx][j], down[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> left = v;
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    int cy = j;
                    while (cy - 1 >= 0 && left[i][cy - 1] == 0)
                        cy--;
                    if (cy - 1 >= 0 && left[i][cy - 1] == left[i][j] && !visited[i][cy - 1]) {
                        left[i][cy - 1] = left[i][j] * 2;
                        left[i][j] = 0;
                        visited[i][cy - 1] = 1;
                    }
                    else
                        swap(left[i][cy], left[i][j]);
                }
            }
            for (int i = 0; i < n; i++)
                visited[i].assign(n, 0);
            vector<vector<int>> right = v;
            for (int i = 0; i < n; i++) {
                for (int j = n - 2; j >= 0; j--) {
                    int cy = j;
                    while (cy + 1 < n&&right[i][cy + 1] == 0)
                        cy++;
                    if (cy + 1 < n&&right[i][cy + 1] == right[i][j] && !visited[i][cy + 1]) {
                        right[i][cy + 1] = right[i][j] * 2;
                        right[i][j] = 0;
                        visited[i][cy + 1] = 1;
                    }
                    else
                        swap(right[i][cy], right[i][j]);
                }
            }
            qu.push(up);
            qu.push(down);
            qu.push(left);
            qu.push(right);
        }
        if (c == 5)
            break;
        c++;
    }
    return ret;
}
int main() {
    scanf("%d", &n);
    vt.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &x);
            vt[i].push_back(x);
        }
    }
    printf("%d\n", bfs());
    return 0;
}