[개쉬운 풀이] 백준 12100 2048 (Easy) CPP (20일차)

문제

 

생각

단순하게 구현 문제라고 생각했지만 구현하는 과정이 쉽지 않았다.

처음 고려한 부분

1. 좌 우 상 하 각각 구현하기

2. 이때 board에 접근 방식에서 좌우, 상하에 따라서 row 부터 접근하는 지, col 부터 접근하는 지 다르다.

3. space를 통해서 옮겼을 때의 빈칸의 위치를 찾으려고 했다.

4. 합쳐졌을 때 같은 숫자인지 판별과 한번 합쳐진 숫자는 더이상 못합쳐지는 것을 중요하게 생각했다.

 

의외의 부분

1. 숫자를 옮기는 과정에서 3중포문을 사용하고 싶지 않아서 2중포문을 사용하려고 했으나, 3중 포문을 통해 빈칸 처리를 해주어야 한다.

2. 5번이 최대로 옮길 수 있는 경우다.

3. row와 col을 접근하는 과정에서 은근 헷갈렸다.

4. 혹시 몰라 long long으로 20x20을 대비했다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#define max(a,b) a > b ? a : b
using namespace std;
typedef long long ll;


const int MAX = 21;

int N;
vector<vector<ll>> map(MAX, vector<ll>(MAX, 0));
ll answer = 0;

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

vector<vector<ll>> move(vector<vector<ll>> board, int dir) {
    vector<vector<bool>> check(N, vector<bool>(N, false));

    if (dir == 0) { // Up
        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N; j++) {
                if (board[j][i] == 0) continue;
                for (int k = j - 1; k >= 0; k--) {
                    if (board[k][i] == board[k + 1][i] && !check[k][i]) {
                        board[k][i] *= 2;
                        board[k + 1][i] = 0;
                        check[k][i] = true;
                        break;
                    } else if (board[k][i] == 0) {
                        board[k][i] = board[k + 1][i];
                        board[k + 1][i] = 0;
                    } else {
                        break;
                    }
                }
            }
        }
    } else if (dir == 1) { // Down
        for (int i = 0; i < N; i++) {
            for (int j = N - 2; j >= 0; j--) {
                if (board[j][i] == 0) continue;
                for (int k = j + 1; k < N; k++) {
                    if (board[k][i] == board[k - 1][i] && !check[k][i]) {
                        board[k][i] *= 2;
                        board[k - 1][i] = 0;
                        check[k][i] = true;
                        break;
                    } else if (board[k][i] == 0) {
                        board[k][i] = board[k - 1][i];
                        board[k - 1][i] = 0;
                    } else {
                        break;
                    }
                }
            }
        }
    } else if (dir == 2) { // Left
        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N; j++) {
                if (board[i][j] == 0) continue;
                for (int k = j - 1; k >= 0; k--) {
                    if (board[i][k] == board[i][k + 1] && !check[i][k]) {
                        board[i][k] *= 2;
                        board[i][k + 1] = 0;
                        check[i][k] = true;
                        break;
                    } else if (board[i][k] == 0) {
                        board[i][k] = board[i][k + 1];
                        board[i][k + 1] = 0;
                    } else {
                        break;
                    }
                }
            }
        }
    } else if (dir == 3) { // Right
        for (int i = 0; i < N; i++) {
            for (int j = N - 2; j >= 0; j--) {
                if (board[i][j] == 0) continue;
                for (int k = j + 1; k < N; k++) {
                    if (board[i][k] == board[i][k - 1] && !check[i][k]) {
                        board[i][k] *= 2;
                        board[i][k - 1] = 0;
                        check[i][k] = true;
                        break;
                    } else if (board[i][k] == 0) {
                        board[i][k] = board[i][k - 1];
                        board[i][k - 1] = 0;
                    } else {
                        break;
                    }
                }
            }
        }
    }
    return board;
}

ll find_value(const vector<vector<ll>>& tmp) {
    ll res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res = max(res, tmp[i][j]);
        }
    }
    return res;
}

void sol(vector<vector<ll>> m, int count) {
    if (count >= 5) {
        answer = max(answer, find_value(m));
        return;
    }

    for (int dir = 0; dir < 4; dir++) {
        vector<vector<ll>> tmp = move(m, dir);
        sol(tmp, count + 1);
    }
}

int main() {
    input();
    sol(map, 0);
    cout << answer << endl;
    return 0;
}