[백준] 12100: 2048_Easy (C++)

12100: 2048_Easy

문제

이 게임은 $N \times N$ 크기 보드에 $2^k$으로 이루어진 블록들이 주어진다. 상, 하, 좌, 우로 움직일 수있으며, 한 턴마다 새로운 숫자 2가 생겨난다. 하지만 문제에서는 새로운 숫자가 생성되지 않음을 가정한다.

이 임의 숫자가 들어간 보드 판에서 최대 5번 이동해서 만들 수 있는 가장 큰 블록 값을 구해야한다.

 

분석

매 턴마다 이동할 수 있는 경우의 수는 상, 하, 좌, 우 4가지이다. 5번의 기회가 주어지니, $4^5=1024$의 경우의 수를 가진다. 대략적으로 모든 경우의 수의 보드를 계산했을 때, $4Byte \times (20 \times 20) \times 1024 = 1.6384\ MB$ 결과가 나오고 메모리 제한은 512MB이다.

따라서 `Brute Force`와 `Backtracking`을 통해 모든 경우의 수를 구할 수 있고, 매 보드마다 최댓값을 갱신해준다. 4-directions마다 넣은 결과를 구하는 방법은 다음과 같다.

1. 원본을 90° 돌린 후, 매 회전마다 `deepcopy`를 반복하여 4-directions 보드를 생성한다. (3번)
2. 매 방향마다 숫자가 한쪽으로 합쳐지는 알고리즘을 적용한다.
3. `dfs()`에 생성된 4개의 보드를 backtracking 방식으로 입력한다.
4. dfs()의 첫 검사마다 최댓값을 갱신해주고, 깊이가 5가되면 종료한다.

필요한 함수들은 다음과 같다.

void input(); // 입력
void output(); // 출력
void dfs(vector<vector<int>> pz2048, int depth); // backtracking
vector<vector<int>> rotate90(vector<vector<int>> board); // 시계방향 90도 회전
vector<vector<int>> &move_left(vector<vector<int>> &board); // 한쪽으로 합치기 (left)
int vec2_max(vector<vector<int>> &board); // 2D 배열 원소 최댓값
void solve(); // 문제 해결 프로세스

`rotate90()`의 경우, board를 복사해야하기 때문에 참조자를 포함하지 않았다. `move_left()`는 합친 후 그대로 사용해야 하기 때문에 참조자 반환을 사용하였다.

1. move_left(): 한쪽으로 합치기

[시행착오: 인덱스 기반 접근의 한계]
이 문제의 가장 핵심 포인트는 위에 나열한 프로세스도 있지만, 개인적으로 나는 한쪽 방향으로 합치는 알고리즘을 만들고 이해하는데 어려움이 있었다. 이전에는 vector의 행을 뒤에서 차례대로 검사하는 방식을 적용했다. 검사하는 원소(arr[n])가 앞에 원소(arr[n-1])랑 같으면 arr[n-1]을 2배하고, arr[n]은 뒤에 있는 원소(arr[n+1])로 덮어준다. 그리고 arr[n+1]의 원소가 배열을 범위를 벗어나면 arr[n]은 0으로 만든다. 이 알고리즘의 가장 치명적인 문제점은 arr[n-1]이 0이고 `arr[n-2] == arr[n]` 이어도 합치지 않는다.

[해결 전략: 추출 후 재배치]
이 알고리즘은 비교 대상(arr[n-1]이 0이어도 더 앞에 있는 숫자(arr[n-2])가 같으면 합치기를 해야 된다. 이 문제를 해결하기 위한 프로세스는 다음과 같다.

1. 0이 아닌 값을 다른 v1(vector)에 저장한다.
2. v1에서 앞 원소를 검사하고 유효한 값에 2배 알고리즘이 적용된 값을 v2(vector)에 채운다.
3. 적용된 크기 v2만큼 원본에 복사하고 나머지는 0으로 채운다.

[예시]
→ 원본: [4, 8, 2, 0, 2, 0, 4, 8]
→ v1: [4, 8, 2, 2, 4, 8] (0 제외 복사)
→ v2: [4, 8, 4, 4, 8] (유효한 값 2배 후 1 건너뛰기)
→ 원본: [4, 8, 4, 4, 8]

vector<vector<int>> &move_left(vector<vector<int>> &board) {
    int N = board[0].size();

    for (int r = 0; r < N; r++) {
        // 1. 0이 아닌값 추출
        vector<int> q;
        for (int c = 0; c < N; c++) {
            if (board[r][c]) {
                q.push_back(board[r][c]);
            }
        }
        
        // 2. 유효한 값 2배 알고리즘 적용
        vector<int> result;
        for (int i = 0; i < q.size(); i++) {
            if (i + 1 < q.size() && q[i] == q[i + 1]) {
                result.push_back(q[i] * 2);
                i++;
            } else {
                result.push_back(q[i]);
            }
        }

        // 3. 원본에 복사
        for (int c = 0; c < N; c++) {
            if (c < result.size())
                board[r][c] = result[c];
            else
                board[r][c] = 0;
        }
    }

    return board;
}

2. rotate90(): 시계 방향으로 90도 회전

4-directions 보드를 복사하기 위해 90도 회전을 진행하는 함수는 다음과 같다. 이때 `deepcopy`가 이루어져야 하기 때문에 인자와 반환값에는 일반 변수를 사용했다. 

vector<vector<int>> rotate90(vector<vector<int>> board) {
    vector<vector<int>> tmp(board);
    int N = board[0].size();

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tmp[c][(N - 1) - r] = board[r][c];
        }
    }

    return tmp;
}

 

여담
행렬곱으로 배열을 회전하는 찾고 싶었지만, 2D, 3D 이상 차원에서는 transpose후 배열을 reverse하는 방식 외에는 찾지 못하였다. 

 

3. dfs(): backtracking으로 1024가지 보드에서 최댓값 갱신

문제의 핵심 프로세스다. 4-directions에 알고리즘을 적용하는 방식은 반복문을 통해 만들어도 되지만 개인적으로 가독성 때문에 반복문을 사용하지 않았다.

void dfs(vector<vector<int>> pz2048, int depth) {
    int target = vec2_max(pz2048);
    if (target > max_num)
        max_num = target;
    if (depth >= 5)
        return;

    auto pz2048_0 = rotate90(pz2048);
    auto pz2048_1 = rotate90(pz2048_0);
    auto pz2048_2 = rotate90(pz2048_1);
    auto pz2048_3 = rotate90(pz2048_2);

    pz2048_0 = move_left(pz2048_0);
    pz2048_1 = move_left(pz2048_1);
    pz2048_2 = move_left(pz2048_2);
    pz2048_3 = move_left(pz2048_3);

    dfs(pz2048_0, depth + 1);
    dfs(pz2048_1, depth + 1);
    dfs(pz2048_2, depth + 1);
    dfs(pz2048_3, depth + 1);
}

`vec2_max()`는 2d-vector에서 최댓값 원소를 찾는 커스텀 함수이다.

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<vector<int>> pz2048;

int max_num = 0;

void input(); // 입력
void output(); // 출력
void dfs(vector<vector<int>> pz2048, int depth); // backtracking
vector<vector<int>> rotate90(vector<vector<int>> board); // 시계방향 90도 회전
vector<vector<int>> &move_left(vector<vector<int>> &board); // 한쪽으로 합치기 (left)
int vec2_max(vector<vector<int>> &board); // 2D 배열 원소 최댓값
void solve(); // 문제 해결 프로세스

void input() {
    cin >> N;
    pz2048.assign(N, vector<int>(N, 0));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            cin >> pz2048[r][c];
        }
    }
}

void dfs(vector<vector<int>> pz2048, int depth) {
    int target = vec2_max(pz2048);
    if (target > max_num)
        max_num = target;
    if (depth >= 5)
        return;

    auto pz2048_0 = rotate90(pz2048);
    auto pz2048_1 = rotate90(pz2048_0);
    auto pz2048_2 = rotate90(pz2048_1);
    auto pz2048_3 = rotate90(pz2048_2);

    pz2048_0 = move_left(pz2048_0);
    pz2048_1 = move_left(pz2048_1);
    pz2048_2 = move_left(pz2048_2);
    pz2048_3 = move_left(pz2048_3);

    dfs(pz2048_0, depth + 1);
    dfs(pz2048_1, depth + 1);
    dfs(pz2048_2, depth + 1);
    dfs(pz2048_3, depth + 1);
}

vector<vector<int>> rotate90(vector<vector<int>> board) {
    vector<vector<int>> tmp(board);
    int N = board[0].size();

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            tmp[c][(N - 1) - r] = board[r][c];
        }
    }

    return tmp;
}

vector<vector<int>> &move_left(vector<vector<int>> &board) {
    int N = board[0].size();

    for (int r = 0; r < N; r++) {
        // 1. 0이 아닌값 추출
        vector<int> q;
        for (int c = 0; c < N; c++) {
            if (board[r][c]) {
                q.push_back(board[r][c]);
            }
        }
        
        // 2. 유효한 값 2배 알고리즘 적용
        vector<int> result;
        for (int i = 0; i < q.size(); i++) {
            if (i + 1 < q.size() && q[i] == q[i + 1]) {
                result.push_back(q[i] * 2);
                i++;
            } else {
                result.push_back(q[i]);
            }
        }

        // 3. 원본에 복사
        for (int c = 0; c < N; c++) {
            if (c < result.size())
                board[r][c] = result[c];
            else
                board[r][c] = 0;
        }
    }

    return board;
}

int vec2_max(vector<vector<int>> &board) {
    int val = 0;
    int N = board[0].size();

    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (board[r][c] > val) {
                val = board[r][c];
            }
        }
    }
    return val;
}

void output() {
    cout << max_num;
    cout << endl;
}

void solve() {
    input();
    dfs(pz2048, 0);
    output();
}

int main() {
    solve();

    return 0;
}

Insight

• 2048 퍼즐게임의 2배 알고리즘은 0을 제외한 원소를 추출하여 2배가 적용된 벡터를 만들고 원본에 복사하여 나머지는 0으로 만든다.

참고자료

1. danbibibi. (2022. 10. 13). [algorithm] 2차원 배열에서 90도 회전 알고리즘. https://velog.io/@danbibibi/2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4%EC%97%90%EC%84%9C-90%EB%8F%84-%ED%9A%8C%EC%A0%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
2. Google. [AI] Gemini: Google의 AI 협업 도구 및 대규모 언어 모델. https://gemini.google.com/