[BOJ] 12100번 - 2048(Easy)

백준 12100번 - 2048(Easy) 

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	40484	10624	5981	24.008%

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

예제는 링크에서 직접 확인해보자.

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

---

예제 입력 1

3
2 2 2
4 4 4
8 8 8

예제 출력 1

16

출처

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

알고리즘 분류

• 구현
• 브루투포스 알고리즘

접근 방법

먼저, 문제를 읽어보면 최대 5번 전체블록들을 (상/하/좌/우) 방향으로 이동 시켜서 블록 하나의 숫자가 제일 큰 것을 찾으라고 한다.

최대 5번 밖에 움직일 수 없으므로, 모든 경우를 탐색해보는 Brute-Force 방식으로 진행해보자.

Backtracking을 할 경우 (move_blocks의 시간복잡도) * $4^5$ 라는 시간복잡도내에 구현할 수 있다.

모든 블록들에 대해 이동 시키는 연산은 최대 $N^3$ 내에 수행할 수 있으므로 N이 20일 때도 무난하게 AC를 받을 수 있을 것이라 생각하고 구현하였다.

 

백트래킹을 위해 DFS를 수행하는 과정에서 이전 상태로 돌아갈 수 있도록, 미리 board의 상태를 저장한 다음 재귀적으로 함수를 호출하면서 해당 함수가 모든 일을 끝마칠 때 다시 원상복구 시키는 방식으로 구현하였다.

 

이 문제에서는 Backtracking 자체가 어려운 것이 아니라, 구현 방법에서 많은 생각을 요구한다.

문제를 잘 읽어보면, 한번의 이동에서 합쳐 진 숫자들은 다시 합쳐지지 않는다는 점과 똑같은 수가 3개가 있을 때 이동하려고 하는 쪽의 칸이 먼저 합쳐진다는 부분이 있다.

여기서 합쳐지는 순서 또한 중요한 요인이라는 것을 염두에 두고 구현을 해보자.

 

 

블록을 이동시킬 때 3가지 경우가 나올 수 있을 것이다.

1. 진행 방향 상에 가장 가까운 블록이 없는 경우

2. 진행 방향 상에 가장 가까운 블록이 있고, 그 값이 다른 경우

3. 진행 방향 상에 가장 가까운 블록이 있고, 그 값이 같은 경우 

 

 

1번 Case 일 때 [ else 구문 ]. 

아마 여기까지 왔다면, pos의. y좌표 혹은 x좌표가 board의 유효범위를 벗어나게 되는 첫 번째 좌표일 것이다.

그러면, 가장 마지막 유효범위는 이동 바로 직전 좌표인 ( pos.first - dy, pos.second - dx ) 가 될 것이다.

이 값은 N-1 이거나 0임을 보장한다.

이 후 pos 좌표에 (i,j)의 값을 이동 시켜준 후, (i,j)의 블록을 비워주면 된다.

( 이 때, 애초에 움직이지 않았을 때를 고려하여 filtering 해준다 )

 

2번 Case 일 때 [ else 구문 ]

1번 case와 로직이 비슷하여 하나로 묶어주었다.

결론부터 말하자면, 1번 case와 2번 case 모두 삽입할 수 있는 블록의 최초 위치를 찾아 해당 블럭 바로 이전 블럭에 삽입하는 구문이다.

2번 case 에서는 while문을 거치면서, pos는 진행 방향으로 움직이며 처음 만나게 되는 최초의 블록의 좌표를 가진다.

이동하고자하는 블록의 값과 진행 방향 상에 있는 블록의 값이 다르므로, pos 바로 이전 블럭으로 이동시켜준다.

 

3번 Case 일 때 [ if 구문 ]

(i,j)에 있는 특정 블록을  pos 에 있는 블록과 합쳐야하는 상황이다.

단, 여기서 한번의 이동 상에서 이미 합쳐진 블록들에 대해서는 다시 합치지 않는다는 조건까지 생각하여 구현해주어야한다.

pos 좌표에 있는  블록의 값을 2배를 시킨다음, (i,j) 에 있는 블록을 비워주는 방식으로 깔끔하게 구현이 가능하다.

 

 

---

 

자, 이제 이러한 과정을 상, 하, 좌, 우 4개의 방향에 대해서 구현을 해주어야한다!

생각해보면, 다 같은 로직인 것을 알 수 있다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다.

유일한 차이점은 위와 같다.

즉, 이동하고자 하는 블록의 순서만 오직 달라진다는 점이다.

필자는 이것을 방향에 따라 index를 부여하는 방식으로 구현하였고 그에 해당 하는 start_row, start_col 을 만들어서 구현하였다.

 

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N;
int board[21][21];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우

int answer;

void move_blocks(int d){
    // 이미 합쳐진 블록을 구분하는 배열이 필요
    bool merged[21][21] = {false, };

    // d 가 왼쪽일 때는 좌측 열부터 시작, d가 오른쪽일 때는 우측 열 부터 시작
    // d 가 위쪽일 때는 윗쪽 행부터 시작, d가 아래쪽일 때는 아래쪽 행 부터 시작
    int start_col = 0 , start_row = 0;
    int di = 1, dj = 1;
    if( d == 1 ) {
        di = -1;
        start_row = N-1;
    }
    if( d == 3 ){
        dj = -1;
        start_col = N-1;
    }


    int dy = dir[d][0], dx = dir[d][1];

    for(int i=start_row; 0 <= i && i < N ; i += di){
        for(int j=start_col; 0 <= j && j < N ; j += dj){
            // pos은 진행방향에서 가장 가까운 블록의 좌표가 된다.
            pair<int, int> pos = {i+dy,j+dx};
            while( 0 <= pos.first && pos.first < N &&
            0 <= pos.second && pos.second < N && board[pos.first][pos.second] == 0){
                pos.first += dy;
                pos.second += dx;
            }

            if( 0 <= pos.first && pos.first < N && 0 <= pos.second && pos.second < N &&
            board[pos.first][pos.second] == board[i][j] &&
            !merged[pos.first][pos.second] ){
                merged[pos.first][pos.second] = true;
                board[pos.first][pos.second] *= 2 ;
                board[i][j] = 0;
            }
            else{
                // pos 이전의 위치에 삽입 ( 진행방향의 반대 방향 )
                int ny = pos.first - dy;
                int nx = pos.second - dx;
                board[ny][nx] = board[i][j] ;
                if( ny != i || nx != j )
                    board[i][j] = 0;
            }
        }
    }
}
void solve(int depth){
    if( depth == 0 ){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) {
                answer = max(answer, board[i][j]);
            }
        }
        return ;
    }

    for(int i=0; i<4; i++){
        int cpy_board[21][21];
        memcpy( cpy_board, board, sizeof(board));
        move_blocks(i);
        solve(depth-1);
        memcpy( board, cpy_board, sizeof(cpy_board));
    }

}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

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

    solve(5);
    cout << answer;

//// test
//    move_blocks(3);
//    for(int i=0; i<N; i++){
//        for(int j=0; j<N; j++)
//            cout << board[i][j] << ' ';
//        cout << '\n';
//    }
    return 0;
}