190407 BOJ 12100번 2048 (Easy)

브루트 포스

- 문제 그대로 구현하면 풀리는 문제 (상하좌우 4가지 경우 * 5번 이동 = 4^5 = 1024 가지 경우의 수)

- 방향에 맞춰 한 줄, 한 칸 씩 확인한다. 

 상으로 이동할 때는 맨 윗칸 부터 아래쪽으로 확인 진행

 하로 이동할 땐 맨 아랫칸 부터 위쪽으로 확인 진행

 좌로 이동할 땐 맨 왼쪽 부터 오른쪽으로 확인 진행

 우로 이동할 땐 맨 오른쪽 부터 왼쪽으로 확인 진행

- 한 이동 사이클 안에서 어떤 블록이 충돌해서 변했을 때, 다시 충돌하지 않도록 해줘야 한다.

- 원소가 하나 남았을 때, 5번 이동했을 때 종료 조건으로 넣어준다.

- 배열이 크지 않으므로 마구마구 완전 탐색 해주면 된다.

소스 코드

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i = a; i < b; i++)
using namespace std;
int N;
int board[21][21];
int real;
int check() {
    int ans = 0;
    FOR(i, 0, N) FOR(j, 0, N) ans = max(ans, board[i][j]);
    return ans;
}
int one() {
    int cnt = 0;
    FOR(i, 0, N) FOR(j, 0, N) if (board[i][j] != 0) cnt++;
    return cnt;
}
void dfs(int cnt) {
    int tmp = one(); //블록이 한 개 남았을 때
    if (cnt == 5 || tmp == 1) {
        real = max(real, check());
        return;
    }
    FOR(k, 0, 4) { //상하좌우
        int de[21][21] = { 0, };
        FOR(i, 0, N) FOR(j, 0, N) de[i][j] = board[i][j];
        switch (k)
        {
        case 0:
            //상
            FOR(i, 0, N) {
                int val = board[0][i]; //가장 근접한 블록의 값
                int val_idx = 0; // 근접한 블록의 인덱스
                FOR(j, 1, N) {
                    if (board[j][i] == 0) continue;
                    else if (board[j][i] == val) {
                        board[val_idx][i] *= 2;
                        board[j][i] = 0;
                        val = -1;
                        val_idx = -1;
                    }
                    else {
                        val = board[j][i];
                        val_idx = j;
                        while (val_idx > 0 && board[val_idx - 1][i] == 0) {
                            int tmp = board[val_idx][i];
                            board[val_idx--][i] = 0;
                            board[val_idx][i] = tmp;
                        }
                    }
                }
            }
            break;
        case 1:
            //하
            FOR(i, 0, N) {
                int val = board[N - 1][i]; //가장 근접한 블록의 값
                int val_idx = N - 1; // 근접한 블록의 인덱스
                for(int j = N - 2; j >= 0; j--) {
                    if (board[j][i] == 0) continue;
                    else if (board[j][i] == val) {
                        board[val_idx][i] *= 2;
                        board[j][i] = 0;
                        val = -1;
                        val_idx = -1;
                    }
                    else {
                        val = board[j][i];
                        val_idx = j;
                        while (val_idx < N - 1 && board[val_idx + 1][i] == 0) {
                            int tmp = board[val_idx][i];
                            board[val_idx++][i] = 0;
                            board[val_idx][i] = tmp;
                        }
                    }
                }
            }
            break;
        case 2:
            //좌
            FOR(i, 0, N) {
                int val = board[i][0]; //가장 근접한 블록의 값
                int val_idx = 0; // 근접한 블록의 인덱스
                FOR(j,1,N) {
                    if (board[i][j] == 0) continue;
                    else if (board[i][j] == val) {
                        board[i][val_idx] *= 2;
                        board[i][j] = 0;
                        val = -1;
                        val_idx = -1;
                    }
                    else {
                        val = board[i][j];
                        val_idx = j;
                        while (val_idx > 0 && board[i][val_idx - 1] == 0) {
                            int tmp = board[i][val_idx];
                            board[i][val_idx--] = 0;
                            board[i][val_idx] = tmp;
                        }
                    }
                }
 
            }
            break;
        case 3:
            //우
            FOR(i, 0, N) {
                int val = board[i][N - 1]; //가장 근접한 블록의 값
                int val_idx = N - 1; // 근접한 블록의 인덱스
                for (int j = N - 2; j >= 0; j--) {
                    if (board[i][j] == 0) continue;
                    else if (board[i][j] == val) {
                        board[i][val_idx] *= 2;
                        board[i][j] = 0;
                        val = -1;
                        val_idx = -1;
                    }
                    else {
                        val = board[i][j];
                        val_idx = j;
                        while (val_idx < N - 1 && board[i][val_idx + 1] == 0) {
                            int tmp = board[i][val_idx];
                            board[i][val_idx++] = 0;
                            board[i][val_idx] = tmp;
                        }
                    }
                }
            }
            break;
        }
        dfs(cnt + 1);
        FOR(i, 0, N) FOR(j, 0, N) board[i][j] = de[i][j]; //원상복귀
    }
}
int main() {
    cin >> N;
    FOR(i, 0, N) FOR(j, 0, N) cin >> board[i][j];

    dfs(0);
    cout << real;
}