https://www.acmicpc.net/problem/12100

백준 12100 - 2048

문제 풀이

보드를 상하좌우로 움직이면서 블록이 최대값이 나올 수 있는 경우를 찾는 문제이다. 한 보드를 상하좌우로 움직이고 원래데로 되돌린 후 다시 시도하기 위해 백트레킹 기법이 필요하다.

• 블록을 상하좌우중 한 방향으로 움직인다.
• 5번 움직이면 블록을 스캔해 최대값을 찾는다.
• 이전 단계로 되돌린 후 다른방향으로 움직이면서 최대값을 찾아본다.

문제 예외 처리

• 한번 합처진 블록은 연속적으로 합처질 수 없다.
• 합처지는 순서는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

int maxValue = 0;
int board[22][22];
int boardSize = 0;

void initBoard(int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cin >> board[i][j];
        }
    }
}

void moveTop() {
    int check[22][22];
    for (int col = 0; col < boardSize; col++) {
        for (int row = 0; row < boardSize; row++) {
            check[col][row] = false;
        }
    }

    for (int row = 0; row < boardSize; row++) {
        for (int col = 0; col < boardSize; col++) {
            int cntRow = row;
            int cntCol = col;

            if (board[cntRow][cntCol] == 0) {
                continue;
            }

            while (cntRow - 1 >= 0 && (board[cntRow - 1][cntCol] == board[cntRow][cntCol] || board[cntRow - 1][cntCol] == 0)) {
                if (board[cntRow - 1][cntCol] == board[cntRow][cntCol]) {
                    if (check[cntRow - 1][cntCol] == false && check[cntRow][cntCol] == false) {
                        board[cntRow - 1][cntCol] += board[cntRow][cntCol];
                        check[cntRow - 1][cntCol] = true;
                        board[cntRow][cntCol] = 0;
                    } else {
                        break;
                    }
                } else {
                    swap(board[cntRow - 1][cntCol], board[cntRow][cntCol]);
                }

                cntRow--;
            }
        }
    }
}

void moveButton() {
    int check[22][22];
    for (int col = 0; col < boardSize; col++) {
        for (int row = 0; row < boardSize; row++) {
            check[col][row] = false;
        }
    }

    for (int row = boardSize - 1; row >= 0; row--) {
        for (int col = 0; col < boardSize; col++) {
            int cntCol = col;
            int cntRow = row;

            if (board[cntRow][cntCol] == 0) {
                continue;
            }

            while (cntRow + 1 < boardSize && (board[cntRow + 1][cntCol] == board[cntRow][cntCol] || board[cntRow + 1][cntCol] == 0)) {
                if (board[cntRow + 1][cntCol] == board[cntRow][cntCol]) {
                    if (check[cntRow + 1][cntCol] == false && check[cntRow][cntCol] == false) {
                        board[cntRow + 1][cntCol] += board[cntRow][cntCol];
                        check[cntRow + 1][cntCol] = true;
                        board[cntRow][cntCol] = 0;
                    } else {
                        break;
                    }
                } else {
                    swap(board[cntRow + 1][cntCol], board[cntRow][cntCol]);
                }

                cntRow++;
            }
        }
    }
}

void moveLeft() {
    int check[22][22];
    for (int col = 0; col < boardSize; col++) {
        for (int row = 0; row < boardSize; row++) {
            check[col][row] = false;
        }
    }

    for (int col = 0; col < boardSize; col++) {
        for (int row = 0; row < boardSize; row++) {
            int cntCol = col;
            int cntRow = row;

            if (board[cntRow][cntCol] == 0) {
                continue;
            }

            while (cntCol - 1 >= 0 && (board[cntRow][cntCol - 1] == board[cntRow][cntCol] || board[cntRow][cntCol - 1] == 0)) {
                if (board[cntRow][cntCol - 1] == board[cntRow][cntCol]) {
                    if (check[cntRow][cntCol - 1] == false && check[cntRow][cntCol] == false) {
                        board[cntRow][cntCol - 1] += board[cntRow][cntCol];
                        check[cntRow][cntCol - 1] = true;
                        board[cntRow][cntCol] = 0;
                    } else {
                        break;
                    }
                } else {
                    swap(board[cntRow][cntCol - 1], board[cntRow][cntCol]);
                }

                cntCol--;
            }
        }
    }
}

void moveRight() {
    int check[22][22];

    for (int col = 0; col < boardSize; col++) {
        for (int row = 0; row < boardSize; row++) {
            check[col][row] = false;
        }
    }

    for (int col = boardSize - 1; col >= 0; col--) {
        for (int row = 0; row < boardSize; row++) {
            int cntRow = row;
            int cntCol = col;

            if (board[cntRow][cntCol] == 0) {
                continue;
            }

            while (cntCol + 1 < boardSize && (board[cntRow][cntCol + 1] == board[cntRow][cntCol] || board[cntRow][cntCol + 1] == 0)) {
                if (board[cntRow][cntCol + 1] == board[cntRow][cntCol]) {
                    if (check[cntRow][cntCol + 1] == false && check[cntRow][cntCol] == false) {
                        board[cntRow][cntCol + 1] += board[cntRow][cntCol];
                        check[cntRow][cntCol + 1] = true;
                        board[cntRow][cntCol] = 0;
                    } else {
                        break;
                    }
                } else {
                    swap(board[cntRow][cntCol], board[cntRow][cntCol + 1]);
                }

                cntCol++;
            }
        }
    }
}

void returnBoard(int (*board)[22], int (*copy)[22]) {
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardSize; j++) {
            board[i][j] = copy[i][j];
        }
    }
}

void moveBoard(int depth) {
    int copyBoard[22][22];
    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardSize; j++) {
            copyBoard[i][j] = board[i][j];
        }
    }

    if (depth == 5) {
        for (int i = 0; i < boardSize; i++) {
            for (int j = 0; j < boardSize; j++) {
                if (board[i][j] > maxValue) {
                    maxValue = board[i][j];
                }
            }
        }
        return;
    }

    moveTop();
    moveBoard(depth + 1);
    returnBoard(board, copyBoard);

    moveButton();
    moveBoard(depth + 1);
    returnBoard(board, copyBoard);

    moveLeft();
    moveBoard(depth + 1);
    returnBoard(board, copyBoard);

    moveRight();
    moveBoard(depth + 1);
    returnBoard(board, copyBoard);
}

int main(void) {
    cin >> boardSize;
    initBoard(boardSize);
    moveBoard(0);

    cout << maxValue << '\n';
    return 0;
}