백준 12100 2048

1. 아이디어를 명확하게 구현하기. 2. 흐름을 말로 설명하고 나서, 코드를 구현하도록 합니다.

/*
12100 2048 풀이
20:36
21:14
38분컷

설계 과정
1. 문제를 꼼꼼히 읽습니다.
2. 설계를 완벽하게 합니다. (예제 3개 돌리기)
3. 경우의 수를 나열합니다.
4. 초기화 변수를 확인합니다.
5. 가지치기를 합니다.
6. 예제와 동일한 변수 선언 및 사용합니다.

풀이 과정
1. 상하좌우에 대해서 dfs 를 돌립니다.
2. 통합함수를 구현합니다.
3. 가장 큰 숫자를 찾습니다.

- 합할때 queue 사용

*/
 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
#define SIZE 22
int map[SIZE][SIZE];
int N;
queue<int> que;
int maxVal;
 
void problemIn() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}
 
void init() {
 
}
 
void copy_map(int(*a)[SIZE], int(*b)[SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            b[i][j] = a[i][j];
        }
    }
}
/*
동 서 남 북

*/
 
void merge(int dir) {
    if (dir == 0) {
        for (int i = 0; i < N; i++) {
            for (int j = N-1; j >= 0; j--) {
                if (map[i][j] == 0) continue;
                que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = N - 1;
            int que_data;
 
            while(!que.empty()){
                que_data = que.front();
                que.pop();
 
                if (map[i][idx] == 0) { // 0 이면,
                    map[i][idx] = que_data;
                    continue;
                }
                else if (map[i][idx] == que_data) { // 같은 숫자를 만나면
                    map[i][idx] *= 2;
                    idx--;
                }
                else { // 다른 숫자를 만나면,
                    idx--;
                    map[i][idx] = que_data; 
                }
            }
        }
    }
 
    else if (dir == 1) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0) continue;
                que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = 0;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
 
                if (map[i][idx] == 0) { // 0 이면,
                    map[i][idx] = que_data;
                    continue;
                }
                else if (map[i][idx] == que_data) { // 같은 숫자를 만나면
                    map[i][idx] *= 2;
                    idx++;
                }
                else { // 다른 숫자를 만나면,
                    idx++;
                    map[i][idx] = que_data;
                }
            }
        }
    }
    else if (dir == 2) {
        for (int j = 0; j < N; j++) {
            for (int i = N - 1; i >= 0; i--) {
                if (map[i][j] == 0) continue;
                que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = N - 1;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
 
                if (map[idx][j] == 0) { // 0 이면,
                    map[idx][j] = que_data;
                    continue;
                }
                else if (map[idx][j] == que_data) { // 같은 숫자를 만나면
                    map[idx][j] *= 2;
                    idx--;
                }
                else { // 다른 숫자를 만나면,
                    idx--;
                    map[idx][j] = que_data;
                }
            }
        }
    }
    else if (dir == 3) {
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < N; i++) {
                if (map[i][j] == 0) continue;
                que.push(map[i][j]);
                map[i][j] = 0;
            }
            int idx = 0;
            int que_data;
 
            while (!que.empty()) {
                que_data = que.front();
                que.pop();
 
                if (map[idx][j] == 0) { // 0 이면,
                    map[idx][j] = que_data;
                    continue;
                }
                else if (map[idx][j] == que_data) { // 같은 숫자를 만나면
                    map[idx][j] *= 2;
                    idx++;
                }
                else { // 다른 숫자를 만나면,
                    idx++;
                    map[idx][j] = que_data;
                }
            }
        }
    }
}
 
void dfs(int depth, int (*map)[SIZE]) {
 
    if (depth == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                maxVal = max(maxVal, map[i][j]);
            }
        }
        return;
    }
 
    int map_store[SIZE][SIZE];
    copy_map(map, map_store);
 
    for (int i = 0; i < 4; i++) {
        merge(i);
        dfs(depth + 1, map);
        copy_map(map_store, map);
    }
}
 
void solve() {
    dfs(0, map);
}
 
int main() {
    problemIn();
    solve();
    cout << maxVal << endl;
    return 0;
}