알고리즘 :: 백준 :: Bruteforce :: 12094:: 2048(Hard)

문제

보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 10번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

문제접근

• https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-12100-2048easy 문제의 심화버전이다. 이동횟수가 기존 5에서 10으로 늘어났는데 시간은 여전히 1초이므로 이전 코드를 빠르게 풀기 위한 최적화 방법을 강구해야한다.

최적화 방법

1. 우선, 벡터는 일반 배열보다 많이 느리다. 벡터를 일반 배열로 바꾼다면 실행속도 측면에서 많이 개선할 수 있다.
2. 만일 이동을 했는데도 이동하기 전과 달라진 것이 없다면 추가로 depth를 늘려서 탐색을 진행하고, 다시 게임판을 원상복귀할 필요가 없다.
3. 만일 이번 depth에서 구할 수 있는 최대 블럭이 다른 재귀에서 구한 최대 블럭보다 작을 것이라 예상된다면 굳이 이번 재귀를 수행할 필요가 없다.

코드

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

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

void action(int actionSelector) {
    queue<int> q;
    switch(actionSelector) {
    case 0: // 왼쪽으로 움직이는 경우
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                if (board[y][x]) q.push(board[y][x]);
                board[y][x] = 0;
            }
            int curRowIdx = 0;      // 현재 i번째 행의 인덱스
            while (!q.empty()) {
                int tempVar = q.front(); q.pop();
                if (board[y][curRowIdx] == 0) board[y][curRowIdx] = tempVar;
                else if (board[y][curRowIdx] == tempVar) board[y][curRowIdx++] += tempVar;
                else board[y][++curRowIdx] = tempVar;
            }
        }
        break;
    case 1: // 오른쪽으로 움직이는 경우
        for (int y = 0; y < N; ++y) {
            for (int x = N - 1; x >= 0; --x) {
                if (board[y][x]) q.push(board[y][x]);
                board[y][x] = 0;
            }
            int curRowIdx = N - 1;  // 우측 끝 인덱스부터 큐에 저장한다.
            while (!q.empty()) {
                int tempVar = q.front(); q.pop();
                if (board[y][curRowIdx] == 0) board[y][curRowIdx] = tempVar;
                else if (board[y][curRowIdx] == tempVar) board[y][curRowIdx--] += tempVar;
                else board[y][--curRowIdx] = tempVar;
            }
        }
        break;
    case 2: // 위쪽으로 움직이는 경우
        for (int x = 0; x < N; ++x) {
            for (int y = 0; y < N; ++y) {
                if (board[y][x]) q.push(board[y][x]);
                board[y][x] = 0;
            }
            int curColIdx = 0;      // 현재 i번째 열의 인덱스
            while (!q.empty()) {
                int tempVar = q.front(); q.pop();
                if (board[curColIdx][x] == 0) board[curColIdx][x] = tempVar;
                else if (board[curColIdx][x] == tempVar) board[curColIdx++][x] += tempVar;
                else board[++curColIdx][x] = tempVar;
            }
        }
        break;
    case 3: // 아래쪽으로 움직이는 경우
        for (int x = 0; x < N; ++x) {
            for (int y = N - 1; y >= 0; --y) {
                if (board[y][x]) q.push(board[y][x]);
                board[y][x] = 0;
            }
            int curColIdx = N - 1;
            while (!q.empty()) {
                int tempVar = q.front(); q.pop();
                if (board[curColIdx][x] == 0) board[curColIdx][x] = tempVar;
                else if (board[curColIdx][x] == tempVar) board[curColIdx--][x] += tempVar;
                else board[--curColIdx][x] = tempVar;
            }
        }
        break;
    }
}
bool isSame(int tmp[20][20]) {
	for (int y = 0; y < N; ++y) 
        for (int x = 0; x < N; ++x)
			if (tmp[y][x] != board[y][x]) return false;
	return true;
}
int findMaxElement() {
    int var = 0;
    for (int y = 0; y < N; ++y) 
        for (int x = 0; x < N; ++x)
            var = max(var, board[y][x]);
    return var;
}
void copyArray(int lhs[][20], int rhs[][20]) {
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            lhs[y][x] = rhs[y][x];
}
void solve(int depth) {
    // [기저 1] - 현재 게임판에서 최대 원소 추출하고, 
    // 현재 depth에서 만들어질 것으로 예상되는 최대 원소보다 작거나 같다면 탐색 불필요.
    int checkCurrMaxValue = findMaxElement();   
    if (checkCurrMaxValue <= maxPerDepth[depth]) return; 
    // [기저 2] - 10번 움직였다면, 최대값 구해서 깊이 별 최대 원소값 갱신한다.
    if (depth == 10) {
        ans = max(ans, checkCurrMaxValue);
        int expectMaxPerDepth = ans;
        while (depth > 0) {
            maxPerDepth[depth--] = expectMaxPerDepth;
            expectMaxPerDepth /= 2;
        }
        return;
    }   
    int currBoard[20][20];
    copyArray(currBoard, board);    // 현재 depth의 게임판을 저장한다.

    for (int i = 0; i < 4; ++i) {   // 취할 수 있는 행동은 4가지
        action(i);                  // 게임판을 움직인 뒤, 변화가 없다면 다음 액션으로 진행.
        if (isSame(currBoard)) continue;
        solve(depth + 1);           // 다음 depth로 이동하고,
        copyArray(board, currBoard);// 완전탐색 원칙에 따라 원상복귀 후 다음 경우의 수(액션) 진행.
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;   // 보드의 크기 (N X N)
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x) 
            cin >> board[y][x];
    ans = findMaxElement();     // ans의 초기값 할당 (안해주면 100%에서 오답. (반례: 1x1 칸일 경우))
    solve(0);
    cout << ans << '\n';
}

결과