[백준/Baekjoon] 12100 2048(easy) C++ :: Implementation

https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

---

1. Logic

- 구현은 항상 느끼는 거지만 문제에 있는 그대로 구현만 잘 하면 된다ㅋㅋㅋㅋ근데 실수하지 않고 구현하는게 어렵다ㅜ

 

풀이 로직을 보자면 한번 키보드를 누를 때 마다 블럭들을 이동시키면서 합칠게 있으면 합쳐줘야한다.

5번 옮길 수 있다고 했기 때문에 재귀를 사용하여 5번 움직이는 동안 블럭들을 상하좌우 옮겨주고 5번이 됐을 때 계산해서 블럭의 Value의 최댓값을 구해주면 된다.

 

블럭을 합쳐주는게 이 문제의 관건인데 나는 큐에 넣어서 처리해줬다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> block(21, vector<int> (21, 0));
int maxValue = -0x3f3f3f3f;

void moveBlock(vector<vector<int>> &board, int type) {
    queue<int> q;
    //0좌 1상 2우 3하
    //좌
    if(type == 0) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j]) {
                    q.push(board[i][j]);
                }
                board[i][j] = 0;
            }

            int idx = 0;

            while(!q.empty()) {
                int num = q.front();
                q.pop();
                if(board[i][idx] == 0) {
                    board[i][idx] = num;
                }
                else if(board[i][idx] == num) {
                    board[i][idx] *= 2;
                    idx++;
                }
                else {
                    idx++;
                    board[i][idx] = num;
                }
            }
        }
    }
    //상
    else if(type == 1) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(board[j][i]) {
                    q.push(board[j][i]);
                }
                board[j][i] = 0;
            }

            int idx = 0;

            while(!q.empty()) {
                int num = q.front();
                q.pop();
                if(board[idx][i] == 0) {
                    board[idx][i] = num;
                }
                else if(board[idx][i] == num) {
                    board[idx][i] *= 2;
                    idx++;
                }
                else {
                    idx++;
                    board[idx][i] = num;
                }
            }
        }
    }
    //우
    else if(type == 2) {
        for(int i = 0; i < n; i++) {
            for(int j = n - 1; j >= 0; j--) {
                if(board[i][j]) {
                    q.push(board[i][j]);
                }
                board[i][j] = 0;
            }

            int idx = n - 1;

            while(!q.empty()) {
                int num = q.front();
                q.pop();
                if(board[i][idx] == 0) {
                    board[i][idx] = num;
                }
                else if(board[i][idx] == num) {
                    board[i][idx] *= 2;
                    idx--;
                }
                else {
                    idx--;
                    board[i][idx] = num;
                }
            }
        }
    }
    //하
    else if(type == 3) {
        for(int i = 0; i < n; i++) {
            for(int j = n - 1; j >= 0; j--) {
                if(board[j][i]) {
                    q.push(board[j][i]);
                }
                board[j][i] = 0;
            }

            int idx = n - 1;

            while(!q.empty()) {
                int num = q.front();
                q.pop();
                
                if(board[idx][i] == 0) {
                    board[idx][i] = num;
                }
                else if(board[idx][i] == num) {
                    board[idx][i] *= 2;
                    idx--;
                }
                else {
                    idx--;
                    board[idx][i] = num;
                }
            }
        }
    }
}

void solve(vector<vector<int>> &board, int cnt) {
    if(cnt == 5) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                maxValue = max(maxValue, board[i][j]);
            }
        }
        return;
    }

    vector<vector<int>> temp = board;

    for(int i = 0; i < 4; i++) {
        moveBlock(board, i);
        solve(board, cnt + 1);
        board = temp;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    

    cin >> n;

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

    solve(block, 0);

    cout << maxValue;
}

 

 

---

3. Feedback

구현문제는 항상 조건을 잘 적어놓고 시작해야 틀리지 않는 것 같다ㅜㅜ 항상 꼼꼼히 조건을 확인하고 풀어야지

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90