12100

백준 12100번

Link: 12100번: 2048 (Easy)

---

문제 설명

일단 내 힘만으로 풀었다는 것부터 적고간다ㅋㅋㅋㅋ

DFS를 통해 모든 경우를 고려해봐야 하는 문제였다.

우선 DFS를 구현하기 전에 map을 어떤 식으로 밀고 같은 수를 합치면 되는지를 먼저 고민해봤다.

여러가지 방법을 생각해보던 중 벡터를 활용해서 옮겨야 하는 수들을 전부 집어넣고 옮긴 다음 옮겨진 수들을 합치는 방법을 생각해 봤다.

그런데 이 방법에는 큰 문제가 있는데, 옮기고 합친 다음 다시 옮겨야 한다는 점이었다.

이를 보완하기 위해 벡터에 옮겨야 하는 수들을 전부 넣고 map을 0으로 바꾼 다음, 그 수들을 비교해서 두 숫자가 같은 숫자이면 합치고 뒤의 숫자를 0으로 바꾼다.

이렇게 벡터의 내용을 바꿔준 다음, 별도로 큐를 정의하여 벡터를 한번 순회하며 0이 아닌 수를 만나면 큐에 넣는다.

마지막으로 옮기는 방향에 맞춰 큐의 내용대로 map을 바꿔주는 방법으로 구현하였다.

메모리상으로는 비효율적이겠지만, 중요한건 시간이니 넘어가자…

이렇게 옮기는 함수를 구현한 다음, DFS를 구현하였다.

이 과정에서 많이 고민했는데, 처음에는 DFS의 인자로 DFS 횟수와 map을 주는 방법으로 구현하였다.

이런식으로 하니 분명 모든 경우의 수를 따지긴 하지만 제출해보니 틀렸는데, 바로 map이 제대로 바뀌지 않는 것이 문제였다.

처음에는 DFS가 제대로 돌지 않는게 아닌가 싶어서 string으로 모든 경우를 다 출력해봤다. 확인 결과 모든 경우 따지는건 맞더라.

여기다 map도 같이 찍어보니 map이 제대로 안바뀌는 문제가 있다는 것을 찾아냈다.

이걸 어떻게 해야 해결할 수 있나 한참 고민하던 중, string으로 찍어본 결과를 이용해보자는 생각을 하게 되었다.

string에 찍힌 대로 DFS의 종료 조건에서 map을 바꾸는 방법을 생각해 냈고, 이대로 구현해보니 시간초과가 났다.

DFS 돌때마다 20*20짜리 배열을 계속 돈다고 생각해보면 시간초과 나는게 당연했다.

이 문제를 해결하기 위해 포인터를 사용했는데, 우선 20*20짜리 배열을 map과 같은 내용을 갖도록 초기화해준 다음 2차원 배열 포인터로 이 배열을 가리키도록 한다.

이 2차원 배열 포인터를 map 바꿔주는 함수의 인자로 전달하여 map을 5번 바꿔준 다음, 앞에서 만든 20*20짜리 배열의 내용을 갱신해준다. 또 갱신 과정에서 최대값도 같이 갱신해준다.

이런식으로 구현하여 제출하니 드디어 맞았다고 나왔다.

DFS로 모든 경우를 다 따져보기만 하면 풀리는 문제였다. 다만 그 경우를 따지기 위한 전처리가 상당히 까다로웠던 문제.

이제 DFS로 푸는 방법을 좀 이해한 것 같다.

문제 풀면서 막히는 부분에 대해 어느 부분에서 막히는지 직접 찾아내고 해결했다는 점에서 매우 뿌듯하다.

앞으로도 이렇게 내 힘만으로 풀어내는 문제들이 많이 있길!!

---

정답 코드

//
// Created by Keith_Lee on 08/02/2019.
//

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

using namespace std;

int N;
int result = 0;
int map[20][20] = {0, };

string progress = "MMMMM";

int (*push(char direction, int (*tempMap)[20]))[20]{ // 이동시킨 후 바뀐 map 리턴.
    // 상
    if(direction == 'U'){
        for(int i=0; i<N; i++){
            vector<int> toMove; // 위로 이동시킬 숫자들
            queue<int> merge; // 이동 후 같은 숫자일때 합치고 저장

            for(int j=0; j<N; j++){
                if(tempMap[j][i] != 0){ // 위로 이동시킬 숫자가 있으면
                    toMove.push_back(tempMap[j][i]); // 벡터에 넣고
                    tempMap[j][i] = 0; // 숫자 자리를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){
                if(j+1 < toMove.size() && toMove[j] == toMove[j+1]){ // 벡터 내에서 같은 숫자가 연속될 경우
                    toMove[j] *= 2; // 합친다
                    toMove[j+1] = 0; // 뒷 숫자를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){ // 벡터를 돌면서
                if(toMove[j] != 0){ // 원소가 0이 아니면
                    merge.push(toMove[j]); // 큐에 넣는다.
                }
            }

            int index = 0;

            while(!merge.empty()){ // 큐를 돌면서
                tempMap[index][i] = merge.front(); // 바뀐 숫자를 맵에 반영한다.
                merge.pop();
                index++;
            }
        }
    }

    // 하
    if(direction == 'D'){
        for(int i=0; i<N; i++){
            vector<int> toMove; // 아래로 이동시킬 숫자들
            queue<int> merge; // 이동 후 같은 숫자일때 합치고 저장

            for(int j=N-1; j>=0; j--){ // 아래쪽부터 돌거임
                if(tempMap[j][i] != 0){ // 아래로 이동시킬 숫자가 있으면
                    toMove.push_back(tempMap[j][i]); // 벡터에 넣고
                    tempMap[j][i] = 0; // 숫자 자리를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){
                if(j+1 < toMove.size() && toMove[j] == toMove[j+1]){ // 벡터 내에서 같은 숫자가 연속될 경우
                    toMove[j] *= 2; // 합친다
                    toMove[j+1] = 0; // 뒷 숫자를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){ // 벡터를 돌면서
                if(toMove[j] != 0){ // 원소가 0이 아니면
                    merge.push(toMove[j]); // 큐에 넣는다.
                }
            }

            int index = 0;

            while(!merge.empty()){ // 큐를 돌면서
                tempMap[N-1-index][i] = merge.front(); // 바뀐 숫자를 맵에 반영한다.
                merge.pop();
                index++;
            }
        }
    }

    // 좌
    if(direction == 'L'){
        for(int i=0; i<N; i++){
            vector<int> toMove; // 왼쪽으로 이동시킬 숫자들
            queue<int> merge; // 이동 후 같은 숫자일때 합치고 저장

            for(int j=0; j<N; j++){
                if(tempMap[i][j] != 0){ // 왼쪽으로 이동시킬 숫자가 있으면
                    toMove.push_back(tempMap[i][j]); // 벡터에 넣고
                    tempMap[i][j] = 0; // 숫자 자리를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){
                if(j+1 < toMove.size() && toMove[j] == toMove[j+1]){ // 벡터 내에서 같은 숫자가 연속될 경우
                    toMove[j] *= 2; // 합친다
                    toMove[j+1] = 0; // 뒷 숫자를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){ // 벡터를 돌면서
                if(toMove[j] != 0){ // 원소가 0이 아니면
                    merge.push(toMove[j]); // 큐에 넣는다.
                }
            }

            int index = 0;

            while(!merge.empty()){ // 큐를 돌면서
                tempMap[i][index] = merge.front(); // 바뀐 숫자를 맵에 반영한다.
                merge.pop();
                index++;
            }
        }
    }

    // 우
    if(direction == 'R'){
        for(int i=0; i<N; i++){
            vector<int> toMove; // 오른쪽으로 이동시킬 숫자들
            queue<int> merge; // 이동 후 같은 숫자일때 합치고 저장

            for(int j=N-1; j>=0; j--){ // 오른쪽부터 돌거임
                if(tempMap[i][j] != 0){ // 오른쪽으로 이동시킬 숫자가 있으면
                    toMove.push_back(tempMap[i][j]); // 벡터에 넣고
                    tempMap[i][j] = 0; // 숫자 자리를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){
                if(j+1 < toMove.size() && toMove[j] == toMove[j+1]){ // 벡터 내에서 같은 숫자가 연속될 경우
                    toMove[j] *= 2; // 합친다
                    toMove[j+1] = 0; // 뒷 숫자를 0으로 만든다.
                }
            }

            for(int j=0; j<toMove.size(); j++){ // 벡터를 돌면서
                if(toMove[j] != 0){ // 원소가 0이 아니면
                    merge.push(toMove[j]); // 큐에 넣는다.
                }
            }

            int index = 0;

            while(!merge.empty()){ // 큐를 돌면서
                tempMap[i][N-1-index] = merge.front(); // 바뀐 숫자를 맵에 반영한다.
                merge.pop();
                index++;
            }
        }
    }

    return tempMap;
}

void DFS(int count){
    if(count == 5){
        int newMap[20][20] = {0, };
        int (*temp)[20] = newMap;

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                newMap[i][j] = map[i][j];
            }
        }

        for(int i=0; i<progress.length(); i++){
            temp = push(progress[i], temp);
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                newMap[i][j] = temp[i][j];
                if(newMap[i][j] > result){
                    result = newMap[i][j];
                }
            }
        }

        return;
    }

    for(int i=1; i<=4; i++){
        if(i == 1){
            progress[count] = 'U';
        }
        else if(i == 2){
            progress[count] = 'D';
        }
        else if(i == 3){
            progress[count] = 'L';
        }
        else if(i == 4){
            progress[count] = 'R';
        }
        DFS(count+1);
    }
}

int main(){
    cin >> N;

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

    DFS(0);

    cout << result << '\n';

    return 0;
}

---