BOJ 12100 : 2048 (Easy)

문제링크

풀이요약

구현

풀이상세

1. 문제에서 구해야 할 내용은 다음과 같다.

   • $_4P_5$ 의 중복 순열을 구해야한다. (방향의 4방향, 경우의 수는 5개, 방향 선택은 중복 가능)
   • 각각의 방향에 대한 이동방법을 구해야한다. 나의 경우, 하나의 방향만 사용하면서 기존의 배열을 4회 회전시켜 다시 탐색하도록 했다.

2. 각각의 방향에 대한 이동방법은 임시 배열을 만들어서, 이전의 값과 동일한 값이 나오는 경우, 이전의 값을 2배로 만들도록 임시 배열을 채운 후, 임시 배열 값을 원래의 배열에 카피하여 반영했다.

3. 5번을 모두 탐색했다면, 현재의 배열 내에서 가장 큰 값을 찾아, 현재 최댓값과 비교한다.

배운점

• 매개변수로 다차원 배열을 사용하는 경우, 포인터로 보내게 되는데 매개변수 자체를 업데이트 하는 과정에서 뭐가 문제인지 안되었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, ans;
vector<vector<int>> v;

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    v.resize(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> v[i][j];
        }
    }
}

int getMax(vector<vector<int>> &curr) {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ret = max(ret, curr[i][j]);
        }
    }
    return ret;
}

void go(vector<vector<int>> &curr) {
    vector<vector<int>> tmp(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        int cIdx = 0;
        bool check = false;
        for (int j = 0; j < N; j++) {
            if (!curr[i][j]) continue;
            if (check && curr[i][j] == tmp[i][cIdx-1]) {
                tmp[i][cIdx-1] *= 2;
                check = false;
            } else {
                tmp[i][cIdx++] = curr[i][j];
                check = true;
            }
        }
        while(cIdx<N) tmp[i][cIdx++] = 0;
    }
    copy(tmp.begin(), tmp.end(), curr.begin());
}

void rotate(vector<vector<int>> &curr) {
    vector<vector<int>> tmp(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            tmp[i][j] = curr[N - j - 1][i];
        }
    }
    copy(tmp.begin(), tmp.end(), curr.begin());
}

void solve(vector<vector<int>> &curr, int cnt) {
    if (cnt >= 5) {
        ans = max(ans, getMax(curr));
        return;
    }

    for (int i = 0; i < 4; i++) {
        vector<vector<int>> tmp(curr);
        go(tmp);
        solve(tmp, cnt + 1);
        rotate(curr);
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve(v, 0);
    output();
}