[백준] 12100. 2048 (easy)

블록을 4방향으로 움직이는데 최대 5번 움직였을때 최댓값을 구하는 문제였다. 

DFS로 몇번 반복할 것인지 설정하고, 방향에 따라 숫자를 합해줬다.

처음에 숫자를 합칠때, 합쳐진것에서 또 합쳐질 수 있도록해서 틀렸는데, 고치니까 바로 맞았다....

2 2 4 2가 왼쪽으로 합쳐진다고하면

4 4 2 가 되야되는데

8 2가 되버리게 한게 잘못이였다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
 
int n;
vector<vector<int>> map;
 
void func(int d) {
    vector<int> t;
    if (d == 0) {//왼
        for (int i = 0; i < n; i++) {
            t.clear();
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0)
                    t.push_back(map[i][j]);
                map[i][j] = 0;
            }
            if (t.size() == 0)
                continue;
            for (int j = 0; j < t.size() - 1; j++) {
                if (t[j] == t[j + 1]) {
                    t[j] *= 2;
                    t.erase(t.begin() + (j + 1));
                }
            }
            for (int j = 0; j < t.size(); j++) {
                map[i][j] = t[j];
            }
        }
    }
    else if (d == 1) {//오
        for (int i = 0; i < n; i++) {
            t.clear();
 
            for (int j = n - 1; j >= 0; j--) {
                if (map[i][j] != 0)
                    t.push_back(map[i][j]);
                map[i][j] = 0;
            }
            if (t.size() == 0)
                continue;
            for (int j = 0; j < t.size() - 1; j++) {
                if (t[j] == t[j + 1]) {
                    t[j] *= 2;
                    t.erase(t.begin() + (j + 1));
                }
            }
            for (int j = 0; j < t.size(); j++) {
                map[i][n - j - 1] = t[j];
            }
        }
    }
    else if (d == 2) {//아래
        for (int i = 0; i < n; i++) {
            t.clear();
 
            for (int j = n - 1; j >= 0; j--) {
                if (map[j][i] != 0)
                    t.push_back(map[j][i]);
                map[j][i] = 0;
            }
            if (t.size() == 0)
                continue;
            for (int j = 0; j < t.size() - 1; j++) {
                if (t[j] == t[j + 1]) {
                    t[j] *= 2;
                    t.erase(t.begin() + (j + 1));
                }
            }
            for (int j = 0; j < t.size(); j++) {
                map[n - j - 1][i] = t[j];
            }
        }
    }
    else if (d == 3) {//위
        for (int i = 0; i < n; i++) {
            t.clear();
 
            for (int j = 0; j < n; j++) {
                if (map[j][i] != 0)
                    t.push_back(map[j][i]);
                map[j][i] = 0;
            }
            if (t.size() == 0)
                continue;
            for (int j = 0; j < t.size() - 1; j++) {
                if (t[j] == t[j + 1]) {
                    t[j] *= 2;
                    t.erase(t.begin() + (j + 1));
                }
            }
            for (int j = 0; j < t.size(); j++) {
                map[j][i] = t[j];
            }
        }
    }
}
int answer = 0;
 
void solution(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer = answer > map[i][j] ? answer : map[i][j];
            }
        }
        return;
    }
    vector<vector<int>> tmp(n, vector<int>(n));
    tmp = map;
    for (int i = 0; i < 4; i++) {
        func(i);
        solution(cnt + 1);
        map = tmp;
    }
    return;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    map.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    //freopen("Input.txt", "r", stdin);
    solution(0);
    cout << answer;
 
    return 0;
}