백준 12100 / 2048 (Easy)

2048 게임

주어지는 상황 (보드의 크기 최대 20x20)에서

최대 5번 굴려서 나오는 가장 큰 블록의 값을 출력하는 문제다.

5번 굴리는 것부터 먼저 정했다.

직전에 풀었던 구슬 게임과는 다르게 같은 방향으로 두번 이동하는 것이 의미가 있기 때문에

총 경우의 수는

4^5=1024번이다.

1024번의 경우의 수에 대해 기울여서 숫자를 모으고 합치는 알고리즘은

1. 사이사이 끼어있는 0을 없앤다. (ex 20204 -> 00224)

2. 옆에있는 숫자가 같을 시 합친다. (ex 00224 -> 00404)

3. 1을 반복한다 (ex 00404 -> 00044)

로 구성했다.

코드 (코드가 굉장히 더럽다. 동,서,남,북으로 기울이는 코드가 서로 다르기때문에 귀찮아도 각각 짰다)

#include<stdio.h>
#include<iostream>
#include<vector>
#include<memory.h>
 
using namespace std;
 
int n;
int orimap[20][20];
int map[20][20];
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
vector<int>dir;
int ans = 0;
 
void move(vector<int>dir) {
 
    //0동 1서 2남 3북
 
    for (int i = 0; i < 5; i++) {
 
        int d = dir[i];
 
        if (d == 0) { // 동
            for (int a = 0; a < n; a++) {
                for (int b = n - 1; b >= 0; b--) {
                    if (map[a][b] == 0) {
                        int now = b;
                        while (now != 0) {
                            now--;
                            if (map[a][now] != 0)break;
                        }
                        map[a][b] = map[a][now];
                        map[a][now] = 0;
                    }
                }
            }
 
            for (int a = 0; a < n; a++) {
                for (int b = n - 1; b >= 1; b--) {
                    if (map[a][b] == map[a][b - 1]) {
                        map[a][b] = 2 * map[a][b];
                        map[a][b - 1] = 0;
                    }
                }
            }
 
            for (int a = 0; a < n; a++) {
                for (int b = n - 1; b >= 0; b--) {
                    if (map[a][b] == 0) {
                        int now = b;
                        while (now != 0) {
                            now--;
                            if (map[a][now] != 0)break;
                        }
                        map[a][b] = map[a][now];
                        map[a][now] = 0;
                    }
                }
            }
        }
        if (d == 1) { //서 
 
            for (int a = 0; a < n; a++) {
                for (int b = 0; b <= n - 1; b++) {
                    if (map[a][b] == 0) {
                        int now = b;
                        while (now != n - 1) {
                            now++;
                            if (map[a][now] != 0)break;
                        }
                        map[a][b] = map[a][now];
                        map[a][now] = 0;
                    }
                }
            }
 
            for (int a = 0; a < n; a++) {
                for (int b = 0; b <= n - 2; b++) {
                    if (map[a][b] == map[a][b + 1]) {
                        map[a][b] = 2 * map[a][b];
                        map[a][b + 1] = 0;
                    }
                }
            }
 
            for (int a = 0; a < n; a++) {
                for (int b = 0; b <= n - 1; b++) {
                    if (map[a][b] == 0) {
                        int now = b;
                        while (now != n - 1) {
                            now++;
                            if (map[a][now] != 0)break;
                        }
                        map[a][b] = map[a][now];
                        map[a][now] = 0;
                    }
                }
            }
 
 
        }
        if (d == 2) { //남
 
            for (int b = 0; b < n; b++) {
                for (int a = n - 1; a >= 0; a--) {
                    if (map[a][b] == 0) {
                        int now = a;
                        while (now != 0) {
                            now--;
                            if (map[now][b] != 0)break;
                        }
                        map[a][b] = map[now][b];
                        map[now][b] = 0;
                    }
                }
            }
 
 
            for (int b = 0; b < n; b++) {
                for (int a = n - 1; a >= 1; a--) {
                    if (map[a][b] == map[a - 1][b]) {
                        map[a][b] = 2 * map[a][b];
                        map[a - 1][b] = 0;
                    }
                }
            }
 
            for (int b = 0; b < n; b++) {
                for (int a = n - 1; a >= 0; a--) {
                    if (map[a][b] == 0) {
                        int now = a;
                        while (now != 0) {
                            now--;
                            if (map[now][b] != 0)break;
                        }
                        map[a][b] = map[now][b];
                        map[now][b] = 0;
                    }
                }
            }
 
 
 
        }
        if (d == 3) { //북
 
            for (int b = 0; b < n; b++) {
                for (int a = 0; a <= n - 1; a++) {
                    if (map[a][b] == 0) {
                        int now = a;
                        while (now != n-1) {
                            now++;
                            if (map[now][b] != 0)break;
                        }
                        map[a][b] = map[now][b];
                        map[now][b] = 0;
                    }
                }
            }
 
            for (int b = 0; b < n; b++) {
                for (int a = 0; a <= n - 2; a++) {
                    if (map[a][b] == map[a + 1][b]) {
                        map[a][b] = 2 * map[a][b];
                        map[a + 1][b] = 0;
                    }
                }
            }
 
            for (int b = 0; b < n; b++) {
                for (int a = 0; a <= n - 1; a++) {
                    if (map[a][b] == 0) {
                        int now = a;
                        while (now != n - 1) {
                            now++;
                            if (map[now][b] != 0)break;
                        }
                        map[a][b] = map[now][b];
                        map[now][b] = 0;
                    }
                }
            }
        }
    }
}
void makedir(int idx) {
    if (idx == 5) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = orimap[i][j];
            }
        }
 
        move(dir);
 
        int max = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (max < map[i][j]) {
                    max = map[i][j];
                }
            }
        }
        if (ans < max) {
            ans = max;
        }
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        dir.push_back(i);
        makedir(idx + 1);
        dir.pop_back();
    }
}
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> orimap[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = orimap[i][j];
        }
    }
 
    makedir(0);
 
 
    cout << ans;
 
}