[C++] 백준 12100 | 2048(Easy)

2048(Easy)

12100번: 2048 (Easy)

---

✍🏻 풀이

2048 게임 👾

5번 안에 만들 수 있는 최대 숫자를 구해내는 문제였다.

아는 게임이라 문제 꼼꼼히 안 읽고 덤볐다가 6%에서 끙끙댔다... 🥹

정신 차리고 반례를 찾아 다녔는데 알고보니 어처구니 없는 실수를 했었다.

 

나는 DFS를 사용하여 탐색을 진행했다! DFS를 돌리다가 깊이가 5가 되면 최댓값을 구하고 전 단계로 돌아가게 하였다.

 

⭐️ 블록을 이동시킬 때마다 보드의 모양이 바뀌기 때문에, 전 단계 보드의 내용을 잘 저장해 주는 것이 중요했던 것 같다.

➡︎ memcpy 함수를 사용하여 배열 내용을 복사해두었다.

 

블록을 이동하는 데에는 상, 하, 좌, 우 네 가지의 방식이 있고 이는 idx로 구분해주었다.

나는 각각을 일일이 구현해주었지만, 검색해보니 보드를 90도씩 돌리리고 공통 연산을 하는 것도 좋은 방법인 것 같다.

---

❗️ 실수한 부분

예를 들어, 보드가 아래와 같은 상태라고 하자.

2	16
4	16	32
32	16	4	1
2	32

이 상태에서 블록을 위로 이동시키면, 

2	32	32	1
4	16	4
32	32
2

이와 같은 상태가 되어야 한다.

 

[ Wrong Answer ] ➡️ 게임을 이렇게 이해하고 구현했다가 계속 틀렸다 🥲

2	16	32	1
4	32	4
32	32
2

 

문제 꼼꼼하게 잘 읽고 이해하고 풀자 !! 🤓

---

✅ Accept Code

#include <bits/stdc++.h>

using namespace std;

int N, ans;
int board[20][20];

queue<int> move(queue<int> Q) {
    queue<int> result;
    int prev = 0;
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        if (prev == 0) {
            prev = cur;
            continue;
        }
        if (prev == cur) {
            result.push(cur * 2);
            prev = 0;
        } else {
            result.push(prev);
            prev = cur;
        }
    }
    if (prev != 0) result.push(prev);
    return result;
}

void moveElem(int board[][20], int idx) {
    if (idx == 0) { // 상
        for (int j = 0; j < N; j++) {
            queue<int> Q;
            for (int i = 0; i < N; i++) {
                if (board[i][j] != 0) Q.push(board[i][j]);
            }
            queue<int> result = move(Q);
            for (int i = 0; i < N; i++) {
                if (!result.empty()) {
                    board[i][j] = result.front();
                    result.pop();
                } else board[i][j] = 0;
            }
        }
    } else if (idx == 1) {   // 하
        for (int j = 0; j < N; j++) {
            queue<int> Q;
            for (int i = N - 1; i >= 0; i--) {
                if (board[i][j] != 0) Q.push(board[i][j]);
            }
            queue<int> result = move(Q);
            for (int i = N - 1; i >= 0; i--) {
                if (!result.empty()) {
                    board[i][j] = result.front();
                    result.pop();
                } else board[i][j] = 0;
            }
        }
    } else if (idx == 2) {   // 좌
        for (int i = 0; i < N; i++) {
            queue<int> Q;
            for (int j = 0; j < N; j++) {
                if (board[i][j] != 0) Q.push(board[i][j]);
            }
            queue<int> result = move(Q);
            for (int j = 0; j < N; j++) {
                if (!result.empty()) {
                    board[i][j] = result.front();
                    result.pop();
                } else board[i][j] = 0;
            }
        }
    } else if (idx == 3) {   // 우
        for (int i = 0; i < N; i++) {
            queue<int> Q;
            for (int j = N - 1; j >= 0; j--) {
                if (board[i][j] != 0) Q.push(board[i][j]);
            }
            queue<int> result = move(Q);
            for (int j = N - 1; j >= 0; j--) {
                if (!result.empty()) {
                    board[i][j] = result.front();
                    result.pop();
                } else board[i][j] = 0;
            }
        }
    }
}

void DFS(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ans = max(ans, board[i][j]);
            }
        }
        return;
    }
    int copyBoard[20][20];
    for (int idx = 0; idx < 4; idx++) {
        memcpy(copyBoard, board, sizeof(board));
        moveElem(board, idx);
        DFS(cnt + 1);
        memcpy(board, copyBoard, sizeof(board));
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    DFS(0);
    cout << ans;
}
/*
[ 해결한 반례 ]

4
2 16 16 0
32 16 4 1
4 16 32 0
2 0 8 8
-> 128

(상)
4
2 16 0 0
4 16 32 0
32 16 4 1
2 32 0 0

(하)
4
2 32 0 0
32 16 4 1
4 16 32 0
2 16 0 0

(좌)
4
2 4 32 2
16 16 16 32
0 32 4 0
0 0 1 0

(우)
4
2 32 4 2
32 16 16 16
0 4 32 0
0 1 0 0

 */