백준 12100 2048(Easy)

이 문제는 각판을 상하좌우로 움직여서 같은 숫자들끼리 합치는 게임입니다. 이때 한번 움직일때는 이미 합쳐진 숫자끼린 합쳐지지 않는 다는점을 주의 하셔야합니다. 2 2 2 2 가있다면 한번 왼쪽으로 움직이면 8 0 0 0 이 아니라 4 4 0 0 이 됩니다. 

 

먼저 5번까지 움직일수 있으므로 5번 움직이는 재귀함수를 하나 작성합니다. 이 함수내부에서 현재의 배열을 각각

상하좌우로 움직여보고 그 결과값을 호출하는 함수에 전달하면 됩니다.

 

상하좌우로 움직이는 코드는  저는 각각 함수로 만들었는데

 

만약 위로 움직인다면 각 열을 기준으로 위에서 부터 아래로 훑으면서 같은 숫자가 있다면 더해서 맨 윗칸에 채우고 다른 숫자라면 이전 숫자를 들어가야 하는 윗칸에 채우는 식으로 채워주었습니다. 

 

아래로 움직인다면 각열을 기준으로 아래에서 부터 위로 훑으면 되고, 왼쪽으로 움직인다면 각 행을 기준으로 왼->오

오른쪽은 각 행을 기준으로 오->왼 으로 훑는 다고 생각하시면 됩니다. 이후 5번을 각각 움직여 주시면 됩니다.

 

#include <bits/stdc++.h>

using namespace std;

int board[21][21];
int N;
int ans;

void up(int cur[21][21]) {

    for(int i = 0; i < N; i++) {
        int idx = 0;
        int prev = -1;
        for(int j = 0; j < N; j++) {
            if(cur[j][i] == 0) continue;

            if(prev == cur[j][i]) {
                cur[idx++][i] = prev*2;
                prev = -1;
                continue;
            }
            else if(prev != -1){
                cur[idx++][i] = prev;
            }
            prev = cur[j][i];
        }

        if(prev != -1) cur[idx++][i] = prev;

        for(int j = idx; j < N; j++)
            cur[j][i] = 0;
    }
    return;
}

void down(int cur[21][21]) {

     for(int i = 0; i < N; i++) {
        int idx = N-1;
        int prev = -1;
        for(int j = N-1; j >= 0; j--) {
            if(cur[j][i] == 0) continue;

            if(prev == cur[j][i]) {
                cur[idx--][i] = prev*2;
                prev = -1;
                continue;
            }
            else if(prev != -1){
                cur[idx--][i] = prev;
            }
            prev = cur[j][i];
        }

        if(prev != -1) cur[idx--][i] = prev;

        for(int j = idx; j >= 0; j--)
            cur[j][i] = 0;
    }
    return;
}

void left(int cur[21][21]) {

    for(int i = 0; i < N; i++) {
        int idx = 0;
        int prev = -1;
        for(int j = 0; j < N; j++) {
            if(cur[i][j] == 0) continue;

            if(prev == cur[i][j]) {
                cur[i][idx++] = prev*2;
                prev = -1;
                continue;
            }
            else if(prev != -1) {
                cur[i][idx++] = prev;
            }
            prev = cur[i][j];

        }
        if(prev != -1) cur[i][idx++] = prev;

        for(int j = idx; j < N; j++)
            cur[i][j] = 0;
    }
    return;
}

void right(int cur[21][21]) {

     for(int i = 0; i < N; i++) {
        int idx = N-1;
        int prev = -1;
        for(int j = N-1; j >= 0; j--) {
            if(cur[i][j] == 0) continue;

            if(prev == cur[i][j]) {
                cur[i][idx--] = prev*2;
                prev = -1;
                continue;
            }
            else if(prev != -1) {
                cur[i][idx--] = prev;
            }
            prev = cur[i][j];

        }
        if(prev != -1) cur[i][idx--] = prev;

        for(int j = idx; j >= 0; j--)
            cur[i][j] = 0;
    }
    return;
}

void sol(int cnt, int cur[21][21]) {

    if(cnt==0) {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                ans = max(ans, cur[i][j]);
        return;
    }

    int cp[4][21][21];

    for(int i = 0; i < 4; i++)
        for(int j = 0; j < N; j++)
            for(int k = 0; k < N; k++)
                cp[i][j][k] = cur[j][k];


    up(cp[0]);
    down(cp[1]);
    left(cp[2]);
    right(cp[3]);

    sol(cnt-1, cp[0]);
    sol(cnt-1, cp[1]);
    sol(cnt-1, cp[2]);
    sol(cnt-1, cp[3]);

    return;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> board[i][j];

    sol(5, board);
    cout<<ans<<'\n';

    return 0;
}