[백준 12100번] 2048(Easy)

문제 링크: https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

<문제 풀이> 시뮬레이션

4가지 이동방향을 구현한 뒤 DFS로 4가지 방향에 대한 모든 경우의 수를 구하면 된다.

한 가지 방향만 잘 구현하면 나머지는 비슷하기에 금방 구현할 수 있다.

 

up방향을 구현할 때 그냥 각 열에 원소를 맨 위 원소부터 시작해서 하나씩 잡고 위로 당겨보면 된다. 

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int N;
int board[20][20];
bool visited[20][20];
int res = 0;
void printBoard() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << "\n\n";
}
 
void up() {
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = i; k >= 1; k--) {
                if (board[k][j] == 0)break;
                if (board[k - 1][j]) {
                    if (!visited[k - 1][j] && board[k-1][j] == board[k][j]) {
                        board[k - 1][j] *= 2;
                        board[k][j] = 0;
                        visited[k - 1][j] = true;
                    }
                    break;
                }
                else {
                    board[k - 1][j] = board[k][j];
                    board[k][j] = 0;
                }
            }
 
        }
    }
    fill(&visited[0][0], &visited[19][20], 0);
}
 
void down() {
    for (int i = N-2; i >=0; i--) {
        for (int j = 0; j < N; j++) {
            for (int k = i; k <= N-2; k++) {
                if (board[k][j] == 0)break;
                if (board[k + 1][j]) {
                    if (!visited[k + 1][j] && board[k + 1][j] == board[k][j]) {
                        board[k + 1][j] *= 2;
                        board[k][j] = 0;
                        visited[k + 1][j] = true;
                    }
                    break;
                }
                else {
                    board[k + 1][j] = board[k][j];
                    board[k][j] = 0;
                }
            }
 
        }
    }
    fill(&visited[0][0], &visited[19][20], 0);
}
void left() {
    for (int j = 1; j < N; j++) {
        for (int i = 0; i < N; i++) {
            for (int k = j; k >= 1; k--) {
                if (board[i][k] == 0)break;
                if (board[i][k-1]) {
                    if (!visited[i][k-1] && board[i][k-1] == board[i][k]) {
                        board[i][k-1] *= 2;
                        board[i][k] = 0;
                        visited[i][k-1] = true;
                        
                    }
                    break;
                    
                }
                else {
                    board[i][k-1] = board[i][k];
                    board[i][k] = 0;
                }
            }
        }
    }
    fill(&visited[0][0], &visited[19][20], 0);
}
 
void right() {
    for (int j = N-2; j >=0; j--) {
        for (int i = 0; i < N; i++) {
            for (int k = j; k <= N-2; k++) {
                if (board[i][k] == 0)break;
                if (board[i][k + 1]) {
                    if (!visited[i][k + 1] && board[i][k + 1] == board[i][k]) {
                        board[i][k + 1] *= 2;
                        board[i][k] = 0;
                        visited[i][k + 1] = true;
                    }
                    break;
                }
                else {
                    board[i][k + 1] = board[i][k];
                    board[i][k] = 0;
                }
            }
        }
    }
    fill(&visited[0][0], &visited[19][20], 0);
}
void dfs(int k) {
    if (k == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = max(res, board[i][j]);             
            }
        }
        return;
    }
    int temp[20][20];
 
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            temp[i][j] = board[i][j];
        }
    }
    up();
    dfs(k + 1);
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            board[i][j] = temp[i][j];
        }
    }
    left();
    dfs(k + 1);
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            board[i][j] = temp[i][j];
        }
    }
    down();
    dfs(k + 1);
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            board[i][j] = temp[i][j];
        }
    }
    right();
    dfs(k + 1);
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            board[i][j] = temp[i][j];
        }
    }
 
}
 
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
 
    dfs(0);
    cout << res;
  
    return 0;
}