12100 : 2048 Easy

formula

판 전체가 중력/바람이 불어 모든 물체가 한 쪽으로 쏠리는 경우
특이 케이스

개별 물체의 경우 dx, dy 사용하지만 전체에 적용될 때 사용

왼쪽으로 쏠림 + Rotate 조합을 통해 4방향 구현

• rotate

// Push 방식 시계 90도 회전 공식
void rotate(Board& board) {
    Board temp = board;

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            board[c][N - 1 - r] = temp[r][c];
        }
    }
}

• shift_left

void shift_left(Board& board) {
    //행 처리
    for (int i = 0; i < N; i++) {
        queue<int> q;

        //열 처리
        for (int j = 0; j < N; j++) {
            if (board[i][j] != 0) {
                q.push(board[i][j]);
            }
            board[i][j] = 0; //빼놓고 비움
        }

        int idx = 0;
        while (!q.empty()) {
            int data = q.front();
            q.pop();
            
            //합쳐지면 변경
            if (!q.empty() && q.front() == data) {
                board[i][idx] = data * 2;
                q.pop();
            }
            else {
                //안되면 그냥 밀린상태로 변경
                board[i][idx] = data;
            }
            //다음 열
            idx++;
        }
    }
}

• 4방향으로 미는 효과 구현

// DFS 5회 4^5 = 1024
void dfs(int cnt, Board board) {

    if (cnt == 5) {
        find_max(board);
        return;
    }

    // 4방향 
    for (int i = 0; i < 4; i++) {
        Board next_board = board;

        // 방향따라 회전
        for (int k = 0; k < i; k++) {
            rotate(next_board);
        }

        shift_left(next_board);
        // Recursive 브루트포스
        dfs(cnt + 1, next_board);
    }
}

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N;
int ans = 0; // 최대값

typedef vector<vector<int>> Board;

void find_max(Board& board) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ans = max(ans, board[i][j]);
        }
    }
}

// Push 방식 시계 90도 회전 공식
void rotate(Board& board) {
    Board temp = board;

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            board[c][N - 1 - r] = temp[r][c];
        }
    }
}

void shift_left(Board& board) {
    //행 처리
    for (int i = 0; i < N; i++) {
        queue<int> q;

        //열 처리
        for (int j = 0; j < N; j++) {
            if (board[i][j] != 0) {
                q.push(board[i][j]);
            }
            board[i][j] = 0; //빼놓고 비움
        }

        int idx = 0;
        while (!q.empty()) {
            int data = q.front();
            q.pop();
            
            //합쳐지면 변경
            if (!q.empty() && q.front() == data) {
                board[i][idx] = data * 2;
                q.pop();
            }
            else {
                //안되면 그냥 밀린상태로 변경
                board[i][idx] = data;
            }
            //다음 열
            idx++;
        }
    }
}

// DFS 5회 4^5 = 1024
void dfs(int cnt, Board board) {

    if (cnt == 5) {
        find_max(board);
        return;
    }

    // 4방향 
    for (int i = 0; i < 4; i++) {
        Board next_board = board;

        // 방향따라 회전
        for (int k = 0; k < i; k++) {
            rotate(next_board);
        }

        shift_left(next_board);
        // Recursive 브루트포스
        dfs(cnt + 1, next_board);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    Board board(N, vector<int>(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }

    dfs(0, board);

    cout << ans << endl;

    return 0;
}