[백준 12100] 2048 (Easy)

 

 

 단순 구현 문제다. 입력 값으로 주어지는 보드의 크기가 상당히 작은 것에서 눈치챌 수 있겠지만 결국 모든 케이스를 탐색해주어야 한다. 나는 탐색은 DFS로 처리해주었고, 단순 구현 부분을 신경써서 작성했다.

 

 각각의 방향으로 움직일 때 보드를 움직이는 코드를 작성해주어야 하는데, 보자마자 떠오르는 직관적인 로직을 그대로 작성하면 된다. 문제에서 주어지는 조건들을 모두 if else 분기처리해서 해결하려 하면, 안 그래도 긴 코드가 더 길어지고 까다롭기 때문에 나는 스택을 이용했다.

 움직이려는 방향이 가로 방향이라면 행 단위로, 세로 방향이라면 열 단위로 한 줄씩 계산한다. 해당 줄에서 목적 방향에 가까운 칸부터 하나씩 확인해서 숫자가 존재한다면 스택을 확인한다. 이 때 스택의 top에 병합할 수 있고 같은 값을 가진 숫자가 있다면 스택에서 pop() 해내고 현재 값의 2배 값을 가진 병합 불가능한 숫자를 스택에 push 한다. 스택이 비어있거나, 병합할 수 없는 숫자가 top에 있다면 현재 값을 그대로 병합 가능한 형태로 push 해주면 된다. 탐색하는 칸에 숫자가 존재하지 않는 경우라면 스택을 확인하지 않고 패스한다.

 이 과정이 끝나면 탐색 중인 줄의 움직임 후 결과 값들이 스택에 쌓여있게 된다. 이를 뒤집어주고(top에 가장 왼쪽에 놓여야 하는 숫자가 존재하므로), 새로 만든 보드의 같은 줄에 있는 움직인 방향에 가까운 칸부터 하나씩 채워준다.

 이를 남은 줄들에 대해서도 반복해준다.

 

 모든 줄에 대해 움직임 처리 및 새로운 보드 생성도 끝났다면, 새로운 보드를 이용해 다음 단계 탐색을 이어가거나 새로운 보드의 원소를 하나씩 탐색해 가장 큰 값을 찾아 리턴한다.

 

 으레 이런 문제들이 그렇지만, 로직 자체는 단순하지만 끝까지 집중하지 않거나 귀찮다고 어림짐작으로 넘어가는 부분이 있으면, 틀리기도 쉽고 틀린 이유 찾아내기도 쉽지가 않은 것 같다. 나도 만들어진 스택을 한 번 뒤집어 주어야 하는 부분을 놓쳐서 찾아내는데 꽤 고생했다.

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int calc(vector<vector<int> > matrix, int direction, int depth) {

    vector<vector<int> > newMatrix(matrix.size(), vector<int>(matrix.size(), 0));

    switch(direction) {
        case 0: {
            //right
            for(int i=0; i<matrix.size(); i++) {
                stack<pair<int, bool> > st; //num, mergeable
                for(int j=matrix.size()-1; j>=0; j--) {
                    if(matrix[i][j]==0) continue;
                    if(!st.empty()&&st.top().first==matrix[i][j]&&st.top().second) {
                        st.pop();
                        st.push({matrix[i][j]*2, false});
                    } else {
                        st.push({matrix[i][j], true});
                    }
                }

                stack<pair<int, bool> > newSt;
                while(!st.empty()) {
                    newSt.push(st.top());
                    st.pop();
                }

                for(int j=matrix.size()-1; j>=0; j--) {
                    if(newSt.empty()) break;
                    newMatrix[i][j] = newSt.top().first;
                    newSt.pop();
                }
            }

            break;
        }
        case 1: {
            //left
            for(int i=0; i<matrix.size(); i++) {
                stack<pair<int, bool> > st; //num, mergeable
                for(int j=0; j<matrix.size(); j++) {
                    if(matrix[i][j]==0) continue;
                    if(!st.empty()&&st.top().first==matrix[i][j]&&st.top().second) {
                        st.pop();
                        st.push({matrix[i][j]*2, false});
                    } else {
                        st.push({matrix[i][j], true});
                    }
                }

                stack<pair<int, bool> > newSt;
                while(!st.empty()) {
                    newSt.push(st.top());
                    st.pop();
                }

                for(int j=0; j<matrix.size(); j++) {
                    if(newSt.empty()) break;
                    newMatrix[i][j] = newSt.top().first;
                    newSt.pop();
                }
            }
            
            break;
        }
        case 2: {
            //up
            for(int i=0; i<matrix.size(); i++) {
                stack<pair<int, bool> > st; //num, mergeable
                for(int j=0; j<matrix.size(); j++) {
                    if(matrix[j][i]==0) continue;
                    if(!st.empty()&&st.top().first==matrix[j][i]&&st.top().second) {
                        st.pop();
                        st.push({matrix[j][i]*2, false});
                    } else {
                        st.push({matrix[j][i], true});
                    }
                }

                stack<pair<int, bool> > newSt;
                while(!st.empty()) {
                    newSt.push(st.top());
                    st.pop();
                }


                for(int j=0; j<matrix.size(); j++) {
                    if(newSt.empty()) break;
                    newMatrix[j][i] = newSt.top().first;
                    newSt.pop();
                }
            }

            break;
        }
        case 3: {
            //down
            for(int i=0; i<matrix.size(); i++) {
                stack<pair<int, bool> > st; //num, mergeable
                for(int j=matrix.size()-1; j>=0; j--) {
                    if(matrix[j][i]==0) continue;
                    if(!st.empty()&&st.top().first==matrix[j][i]&&st.top().second) {
                        st.pop();
                        st.push({matrix[j][i]*2, false});
                    } else {
                        st.push({matrix[j][i], true});
                    }
                }

                stack<pair<int, bool> > newSt;
                while(!st.empty()) {
                    newSt.push(st.top());
                    st.pop();
                }

                for(int j=matrix.size()-1; j>=0; j--) {
                    if(newSt.empty()) break;
                    newMatrix[j][i] = newSt.top().first;
                    newSt.pop();
                }
            }

            break;
        }
    }

    int largestNum = 0;

    if(depth == 5) {
        for(int i=0; i<matrix.size(); i++) {
            for(int j=0; j<matrix.size(); j++) {
                largestNum = max(largestNum, newMatrix[i][j]);
            }
        }

        return largestNum;
    } else {
        for(int i=0; i<4; i++) {
            largestNum = max(largestNum, calc(newMatrix, i, depth+1));
        }

        return largestNum;
    }
}

int main() {
    int n;
    cin >> n;

    vector<vector<int> > matrix(n, vector<int>(n));

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

    int maxNum = 0;
    for(int i=0; i<4; i++) {
        maxNum = max(maxNum, calc(matrix, i, 1));
    }
    
    cout << maxNum;

}