2048 (Easy) 12100

문제

생략

접근 방법

엄청 많은 경우가 나올 것 같지만 4방향으로 5번 이동하는 것이기에 큰 경우의 수는 아니다.
즉 모든 경우를 확인해 보는 구현 문제이다.
4방향을 이동시킬 때 하드코딩 해서 4방향을 시도할 수 있고 나도 그렇게 풀려다 회전시키면 같은 동작인 것 같아서 회전시키는 방식으로 해결했다.
이동을 구현할 때는 비어있는 보드를 추가로 사용하여 첫 공간부터 차례대로 넣는 방식으로 구현했다. 이렇게 하면 0부터 순서대로 쌓이기에 이동시킨 것과 동일한 동작을 한다. 또한 이미 사용한 값을 또 사용할 일도 없다. (보드가 다르기 때문이다)
만약 근접한 두 값이 같은 값이면 합쳐서 다음에 사용할 보드에 집어넣어 준다. 이후 마지막 값에 다음 값부터 확인하면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N, ret;
vector<vector<int>> temp;
void dfs(int depth, vector<vector<int>> map);
void rotate(vector<vector<int>> &map)
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            temp[j][N - 1 - i] = map[i][j];
    map = temp;
}
void left(int depth, vector<vector<int>> &map)
{
    vector<vector<int>> nextMap = vector<vector<int>>(N, vector<int>(N));
    for (int i = 0; i < N; ++i) // 세로
    {
        int k = 0;
        for (int j = 0; j < N; ++j) // 가로
            if (map[i][j])          // 왼쪽 값이 존재한다면
                if (j + 1 == N)     // 끝에 값
                    nextMap[i][k] = map[i][j];
                else
                {
                    int l = j + 1;
                    for (; l < N; ++l)
                        if (map[i][l])
                            break;
                    if (map[i][j] == map[i][l])
                    {
                        nextMap[i][k++] = map[i][j] * 2;
                        j = l;
                    }
                    else
                    {
                        nextMap[i][k++] = map[i][j];
                        j = l - 1;
                    }
                }
    }
    dfs(depth + 1, nextMap);
}
void dfs(int depth, vector<vector<int>> map)
{
    if (depth == 5)
    {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                ret = max(map[i][j], ret);
        return;
    }
    left(depth, map);
    for (int i = 0; i < 3; ++i)
    {
        rotate(map);
        left(depth, map);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    vector<vector<int>> map;
    map = temp = vector<vector<int>>(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> map[i][j];
    dfs(0, map);
    cout << ret;
    return 0;
}

풀이

4퍼센트에서 계속 틀렸었다.
이유는 한가지 실수를 했었는데 근접한 두 값을 확인할 때 바로 옆에 값만 확인했기 때문이다. 두 값 사이에는 공백이 존재할 수 있다.
그렇기에 공백을 건너뛴 다음의 값을 확인해야 한다.