[백준 12100] 2048 (Easy) (삼성 SW 역량 테스트 기출 문제)

# 문제 링크

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

# 접근 방법

문제를 보자마자 재귀함수를 통해 up, down, left, right 네 가지 방향을 탐색하고 재귀함수의 깊이가 5가 되면 최댓값을 업데이트해주는 방식으로 해야겠다고 생각했다.

 

# 신경써야 할 부분

한 번 옮길 때, 각 블록들은 한 번만 합쳐질 수 있다. 예를 들어 다음과 같은 상황에서 위로 한 번 옮기면

2	2	2	2
2	2	2	2
2	2	2	2
2	2	2	2

               ⬇️

4	4	4	4
4	4	4	4
0	0	0	0
0	0	0	0

이렇게 변한다. 1열과 2열에 같은 값이 남았더라도 또 합쳐주지 않는다.

또, 중간에 빈 칸이 있는 경우를 생각해줘야 한다. 무작정 인접한 값과 비교한다면 원하는 답을 얻을 수 없을 것이다. 따라서 나는 deque 자료구조를 이용했다. 각 열 또는 행에서 각 값이 0이 아니고 deque가 비어있지 않다면 deque의 back 값과 비교해주고 같다면 back 값을 pop하고 합친 값을 넣어주었다. 이 때, 한 번 합쳐진 값은 또 합쳐지면 안되기 때문에, deque 안에서 합쳐진 원소를 가리키는 combined_top 변수를 활용했다.

 

# 소스코드

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

const int MAX = 20;
const int MOVE_MAX = 5;
int n;
int max_value;

vector<vector<int>> up(vector<vector<int>> board);
vector<vector<int>> down(vector<vector<int>> board);
vector<vector<int>> left(vector<vector<int>> board);
vector<vector<int>> right(vector<vector<int>> board);
void slide(vector<vector<int>> board, int move_cnt);

int main() {
    scanf("%d", &n);
    
    vector<vector<int>> board(n);
    
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            int input;
            scanf("%d", &input);
            board[r].push_back(input);
        }
    }
    
    slide(board, 0);
    printf("%d\n", max_value);
    
    return 0;
}

void slide(vector<vector<int>> board, int move_cnt) {
    if (move_cnt == 5) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] > max_value) max_value = board[r][c];
            }
        }
        return;
    }
    
    vector<vector<int>> board_next;
    
    board_next = up(board);
    slide(board_next, move_cnt + 1);

    board_next = down(board);
    slide(board_next, move_cnt + 1);

    board_next = left(board);
    slide(board_next, move_cnt + 1);

    board_next = right(board);
    slide(board_next, move_cnt + 1);
}

vector<vector<int>> up(vector<vector<int>> board) {
    for (int c = 0; c < n; c++) {
        deque<int> deq;
        int combined_top = -1;
        
        for (int r = 0; r < n; r++) {
            if (board[r][c]) {
                if (!deq.empty() && deq.back() == board[r][c] && combined_top != deq.size()) {
                    deq.pop_back();
                    deq.push_back(board[r][c] << 1);
                    combined_top = deq.size();
                }
                else
                    deq.push_back(board[r][c]);
            }
            board[r][c] = 0;
        }
        
        int deq_size = deq.size();
        for (int r = 0; r < deq_size; r++) {
            board[r][c] = deq.front();
            deq.pop_front();
        }
    }
    return board;
}

vector<vector<int>> down(vector<vector<int>> board) {
    for (int c = 0; c < n; c++) {
        deque<int> deq;
        int combined_top = -1;
        
        for (int r = n - 1; r >= 0; r--) {
            if (board[r][c]) {
                if (!deq.empty() && deq.back() == board[r][c] && combined_top != deq.size()) {
                    deq.pop_back();
                    deq.push_back(board[r][c] << 1);
                    combined_top = deq.size();
                }
                else
                    deq.push_back(board[r][c]);
            }
            board[r][c] = 0;
        }
        
        int deq_size = deq.size();
        for (int r = 0; r < deq_size; r++) {
            board[n - 1 - r][c] = deq.front();
            deq.pop_front();
        }
    }
    return board;
}

vector<vector<int>> left(vector<vector<int>> board) {
    for (int r = 0; r < n; r++) {
        deque<int> deq;
        int combined_top = -1;
        
        for (int c = 0; c < n; c++) {
            if (board[r][c]) {
                if (!deq.empty() && deq.back() == board[r][c] && combined_top != deq.size()) {
                    deq.pop_back();
                    deq.push_back(board[r][c] << 1);
                    combined_top = deq.size();
                }
                else
                    deq.push_back(board[r][c]);
            }
            board[r][c] = 0;
        }
        
        int deq_size = deq.size();
        for (int c = 0; c < deq_size; c++) {
            board[r][c] = deq.front();
            deq.pop_front();
        }
    }
    return board;
}

vector<vector<int>> right(vector<vector<int>> board) {
    for (int r = 0; r < n; r++) {
        deque<int> deq;
        int combined_top = -1;
        
        for (int c = n - 1; c >= 0; c--) {
            if (board[r][c]) {
                if (!deq.empty() && deq.back() == board[r][c] && combined_top != deq.size()) {
                    deq.pop_back();
                    deq.push_back(board[r][c] << 1);
                    combined_top = deq.size();
                }
                else
                    deq.push_back(board[r][c]);
            }
            board[r][c] = 0;
        }
        
        int deq_size = deq.size();
        for (int c = 0; c < deq_size; c++) {
            board[r][n - 1 - c] = deq.front();
            deq.pop_front();
        }
    }
    return board;
}