[ 백준 12100 ] 2048 Easy (C++) - DFS, 브루트포스, 구현

---

🔗 문제 링크

12100번: 2048 (Easy)

---

💡 문제 풀이 및 해석

1. 일단, 맵의 크기와 반복 횟수가 5인 점을 감안하면 브루트 포스하게 풀 수 있다고 생각했다. (매번 맵을 복사 하면서)
2. 상하좌우 움직이는 모형을 구현해야 한다.
   2-1. 순서대로 이동하는 것이니 0을 제외하고 모두 받아온다.
   2-2. 순서대로 쌓아 올린다.
   2-3. 이때, 같은 칸(같은 index)에 쌓아 올릴 때, 같은 숫자면 더해주고 다음 칸으로 넘어간다.
   2-4. 칸은 칸에 쌓아 올릴 때, 다른 숫자면 다음 칸에 쌓아준다.
3. 2번 방식으로 상하좌우를 만들어준다.
4. 매번 현재 상태의 Board를 복제하여 상하좌우로 보낸다.
5. 상하좌우로 보내진 Board를 DFS로 보낸다.
6. 마지막 시행 시 모든 보드의 칸을 탐색하여 최대의 칸을 찾는다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

int N;
int myMap[21][21];
int answer = 0;
queue<int> q;

void input() {
    cin >> N;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> myMap[y][x];
        }
    }
}

void up() {
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            if (myMap[y][x] == 0) continue;
            q.push(myMap[y][x]);
            myMap[y][x] = 0;
        }
        int index = 1;
        while (!q.empty()) {
            int num = q.front(); q.pop();
            if (myMap[index][x] == 0) myMap[index][x] = num;
            else {
                if (myMap[index][x] == num) myMap[index++][x] *= 2;
                else {
                    myMap[++index][x] = num;
                }
            }
        }
    }
}

void down() {
    for (int x = 1; x <= N; x++) {
        for (int y = N; y >= 1; y--) {
            if (myMap[y][x] == 0) continue;
            q.push(myMap[y][x]);
            myMap[y][x] = 0;
        }
        int index = N;
        while (!q.empty()) {
            int num = q.front(); q.pop();
            if (myMap[index][x] == 0) myMap[index][x] = num;
            else {
                if (myMap[index][x] == num) myMap[index--][x] *= 2;
                else {
                    myMap[--index][x] = num;
                }
            }
        }
    }
}

void left() {
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            if (myMap[y][x] == 0) continue;
            q.push(myMap[y][x]);
            myMap[y][x] = 0;
        }
        int index = 1;
        while (!q.empty()) {
            int num = q.front(); q.pop();
            if (myMap[y][index] == 0) myMap[y][index] = num;
            else {
                if (myMap[y][index] == num) myMap[y][index++] *= 2;
                else {
                    myMap[y][++index] = num;
                }
            }
        }
    }
}

void right() {
    for (int y = 1; y <= N; y++) {
        for (int x = N; x >= 1; x--) {
            if (myMap[y][x] == 0) continue;
            q.push(myMap[y][x]);
            myMap[y][x] = 0;
        }
        int index = N;
        while (!q.empty()) {
            int num = q.front(); q.pop();
            if (myMap[y][index] == 0) myMap[y][index] = num;
            else {
                if (myMap[y][index] == num) myMap[y][index--] *= 2;
                else {
                    myMap[y][--index] = num;
                }
            }
        }
    }
}

void move(int dir) {

    switch (dir)
    {
    case 1:
        right();
        break;
    case 2:
        left();
        break;
    case 3:
        down();
        break;
    case 4:
        up();
        break;
    default:
        break;
    }

}

void dfs(int cnt) {
    if (cnt == 0) return;

    int tempMap[21][21];
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            tempMap[y][x] = myMap[y][x];
        }
    }

    for (int dir = 1; dir <= 4; dir++) {
        move(dir);
        for (int y = 1; y <= N; y++) {
            for (int x = 1; x <= N; x++) {
                answer = max(answer, myMap[y][x]);
            }
        }
        dfs(cnt - 1);
        for (int y = 1; y <= N; y++) {
            for (int x = 1; x <= N; x++) {
                myMap[y][x] = tempMap[y][x];
            }
        }
    }
}

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

    input();
    dfs(5);

    cout << answer;

    return 0;
}

---

🤔 문제 후기

문제를 푸는 아이디어 자체는 어렵지 않았다... 그런데, 이렇게 막 풀어도 되는 건가? 싶은 문제였다. 사실, 최악의 경우는 시간초과가 난다고 생각했는데, 생각보다 원활하게 통과해서 놀랐다. 그런데 Hard 문제처럼 움직이는 횟수가 늘어난다면, 어떻게 최적화를 해야 할지 좀 난감한 문제였다.