[백준] 12100 2048 (Easy)

12100번: 2048 (Easy)

 

www.acmicpc.net

풀이

블록의 움직임을 구현하고, 완전탐색으로 모든 경우를 시도해보면 되는 문제이다. 이 문제의 포인트는 블럭을 이동시키는 것과 완전탐색을 구현하는 것이다.
블럭을 이동시키는 것은 상하좌우 4방향을 구현해야하는데, 한 방향을 구현해두면 보드를 회전시켜 다른 방향을 쉽게 구현할 수 있다.

void rotate_board() {
    vector<vector<int>> tmp = board;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            board[i][j] = tmp[n - 1 - j][i];
}

보드를 시계방향으로 90도 회전하는 함수는 위와 같은데, 알아두면 유용하니 숙지하기를 추천한다.

보드를 회전시키는 함수를 구현했으니 위쪽 방향으로 블록을 이동시키는 함수를 보자. 주석을 확인해보면 쉽게 이해할 수 있을 것이다. 이 때 현재 위치가 비어있으면 아래에 있는 블록을 찾아서 현재 위치로 옮기고, 옮긴 블록과 같은 값을 가진 블록을 찾아 합칠 수 있도록 if~else문이 아닌 if문을 2번 사용해서 구현하였다.

void up() {
    for (int j = 0; j < n; j++) {
        // 맨 위부터 n-2까지 탐색
        for (int i = 0; i < n - 1; i++) {
            // 현재 블록 바로 아래에 있는 블록부터 시작
            int y = i + 1;
            // 현재 블록이 0인 경우
            if (!board[i][j]) {
                // 0이 아닌 블록이 나올 때까지 탐색한다
                while (y < n && board[y][j] == 0) y++;
                // 보드 밖으로 벗어나지 않은 경우 찾은 블록을 현재 위치로 옮긴다
                if (y < n) {
                    board[i][j] = board[y][j];
                    board[y][j] = 0;
                }
            }
            // 현재 블록이 0이 아닌 경우
            if (board[i][j]) {
                // 0이 아닌 블록이 나올 때까지 탐색한다
                while (y < n && board[y][j] == 0) y++;
                // 보드 밖으로 벗어나지 않고, 현재 블록과 같은 값인 경우
                if (y < n && board[y][j] == board[i][j]) {
                    // 현재 블록의 크기를 2배로 한다
                    board[i][j] *= 2;
                    // 찾은 블록은 0으로 변경
                    board[y][j] = 0;
                    // 최대값 비교
                    ans = max(ans, board[i][j]);
                }
            }            
        }
    }
}

완전 탐색은 백트래킹을 사용하여 구현하였다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, ans;
vector<vector<int>> board, tmp;
vector<int> op;

void rotate_board() {
    vector<vector<int>> tmp = board;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            board[i][j] = tmp[n - 1 - j][i];
}

void up() {
    for (int j = 0; j < n; j++) {
        // 맨 위부터 n-2까지 탐색
        for (int i = 0; i < n - 1; i++) {
            // 현재 블록 바로 아래에 있는 블록부터 시작
            int y = i + 1;
            // 현재 블록이 0인 경우
            if (!board[i][j]) {
                // 0이 아닌 블록이 나올 때까지 탐색한다
                while (y < n && board[y][j] == 0) y++;
                // 보드 밖으로 벗어나지 않은 경우 찾은 블록을 현재 위치로 옮긴다
                if (y < n) {
                    board[i][j] = board[y][j];
                    board[y][j] = 0;
                }
            }
            // 현재 블록이 0이 아닌 경우
            if (board[i][j]) {
                // 0이 아닌 블록이 나올 때까지 탐색한다
                while (y < n && board[y][j] == 0) y++;
                // 보드 밖으로 벗어나지 않고, 현재 블록과 같은 값인 경우
                if (y < n && board[y][j] == board[i][j]) {
                    // 현재 블록의 크기를 2배로 한다
                    board[i][j] *= 2;
                    // 찾은 블록은 0으로 변경
                    board[y][j] = 0;
                    // 최대값 비교
                    ans = max(ans, board[i][j]);
                }
            }
        }
    }
}

void right() {
    for (int i = 0; i < 3; i++) rotate_board();
    up();
    rotate_board();
}

void left() {
    rotate_board();
    up();
    for (int i = 0; i < 3; i++) rotate_board();
}

void down() {
    for (int i = 0; i < 2; i++) rotate_board();
    up();
    for (int i = 0; i < 2; i++) rotate_board();
}

void dfs(int cnt) {
    if (cnt == 5) {
        board = tmp;
        for (int i : op) {
            if (i == 0) up();
            else if (i == 1) right();
            else if (i == 2) down();
            else if (i == 3) left();
        }
        return;
    }

    for (int i = 0; i < 4; i++) {
        op.push_back(i);
        dfs(cnt + 1);
        op.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    board = vector<vector<int>>(n, vector<int>(n));
    tmp = vector<vector<int>>(n, vector<int>(n));

    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            cin >> tmp[i][j];
            ans = max(ans, tmp[i][j]);
        }
    dfs(0);    
    cout << ans << '\n';
    return 0;
}