BOJ 12100 - 2048(Easy)(C++)

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

풀이

상하좌우를 이용한 5번 이동에 모든 경우의 수를 탐색

해당 경우에 대해 이동(상하좌우 모든 경우에 대한 이동을 구현하지 않고 위로 이동에 대한 이동만 구현)

  - 상하좌우에 따라 회전

     - 상 : 0˚, 하: 180˚, 좌 : 90˚, 우: 270˚ 

  - 위로 이동

  - 다시 제자리로 회전

     - 상 : 0˚, 하: 180˚, 좌 : 270˚, 우: 90˚

  - 5번의 이동이 끝나면 행렬의 값으로 최대값 갱신

ex) 우로 이동

 

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> map;
int N;
int MAX = 0;

void move(vector<vector<int>>& arr) {//위로 블록을 이동
    for (int x = 0; x < N; x++) {
        vector<int> v;
        v.push_back(0);
        bool flag = false;
        for (int y = 0; y < N; y++) {
            if (arr[y][x] == 0)continue;
            if (v[v.size() - 1] == arr[y][x]&&!flag) {//이미 합쳐진 블록은 합쳐질 수 X
                v[v.size() - 1] *= 2;
                flag = true;
            }
            else {
                v.push_back(arr[y][x]);
                flag = false;
            }
        }
        for (int i = 1; i < v.size(); i++) {
            arr[i - 1][x] = v[i];
        }
        for (int i = v.size() - 1; i < N; i++) {
            arr[i][x] = 0;
        }
    }
}

void rotate(vector<vector<int>>& arr, int cnt) {//시계방향 90도 회전
    vector<vector<int>> temp(N, vector<int>(N));
    for (int idx = 0; idx < cnt; idx++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                temp[j][N-i-1] = arr[i][j];
            }
        }
        arr = temp;
    }
}


int cal_score(vector<vector<int>> &arr) {
    int max = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            max = arr[i][j] > max ? arr[i][j] : max;
        }
    }
    return max;
}

void go(vector<int> seq) {
    vector<vector<int>> arr = map;
    for (auto cmd:seq) {
        if (cmd == 0) {//위로 이동
            move(arr);
        }
        else if (cmd == 1) {//밑으로 이동
            rotate(arr, 2);
            move(arr);
            rotate(arr, 2);
        }
        else if (cmd == 2) {//좌
            rotate(arr, 1);
            move(arr);
            rotate(arr, 3);
        }
        else  {//우
            rotate(arr, 3);
            move(arr);
            rotate(arr, 1);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            MAX = arr[i][j] > MAX ? arr[i][j] : MAX;
        }
    }
}

void decide_seq(vector<int> seq) {
    if (seq.size() == 5) {
        go(seq);
        return;
    }
    for (int i = 0; i < 4; i++) {
        seq.push_back(i);
        decide_seq(seq);
        seq.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> N;
    map.resize(N, vector<int>(N, 0));
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    
    decide_seq(vector<int> ());
    cout << MAX;

    return 0;
}