[12100번] 2048 (Easy) (삼성코딩테스트)

문제

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

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

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

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

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

 

문제접근법.

 

1. 블록을 옮기기 위한 코드를 구현해야 한다. 블록을 옮기기 위해서, 기존의 칸을 비워두고 칸의 열 혹은 행의 정보를 가지고 WHILE문을 사용한다. 앞에 블록이 없다면 이동하고, 있다면 멈춘다. 벽에 부딪힌 것이 아니라면, 해당 방향에 맞추어서 앞에 있는 블록에 대해서 비교해준다. 합쳐진다면 합치고 최댓값을 갱신하고 체크 배열에 값을 넣어준다.

 

2. 4방향으로 5번 완전 탐색이 필요하므로, DFS를 사용해준다. 배열을 이동마다 저장이 되어야 하므로 백트래킹이 적절하다.

 

1번을 가장 잘 구현해야 한다. 1번을 구현해보고 방향마다 정확하게 이동되는지 체크가 필요하다. 또한, for문 배열에서 변수가 혼용되지 않게 주의하고, for문에 변수값들을 이용할 때, temp 변수를 사용해서 기존의 값이 변경되지 않도록 한다.

 

해설코드(C++).

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
int arr[21][21] = { 0 };
int answer = 0;
 
void dfs(int n) {
    if (n == 5)
        return;
 
    int val = 0;
    
    // BACKTRACKING
    int tmp[21][21] = { 0 };
    memcpy(tmp, arr, sizeof(arr));
    
    for (int i = 0; i < 4; i++) {
        int check[21][21] = { 0 };
        memset(check, 0, sizeof(check));
 
        // MOVE UP
        if (i == 0) {
            for (int r = 1; r <= N; r++) {
                for (int c = 1; c <= N; c++) {
                    if (arr[r][c] != 0) {
                        int temp = r;
                        val = arr[r][c];
                        arr[r][c] = 0;
 
                        while (temp > 1) {
                            if (arr[temp - 1][c] == 0)
                                temp--;
                            else
                                break;
                        }
 
                        if (temp > 1) {
                            if (arr[temp - 1][c] == val && check[temp - 1][c] == 0)
                            {
                                answer = max(answer, 2 * val);
                                arr[temp - 1][c] *= 2;
                                check[temp - 1][c] = 1;
                            }
                            else
                                arr[temp][c] = val;
                        }
                        else {
                            arr[temp][c] = val;
                        }
                    }
                }
            }
        }
        // MOVE DOWN
        else if (i == 1) {
            for (int r = N; r >= 1; r--) {
                for (int c = 1; c <= N; c++) {
                    if (arr[r][c] != 0) {
                        int temp = r;
                        val = arr[r][c];
                        arr[r][c] = 0;
 
                        while (temp < N) {
                            if (arr[temp + 1][c] == 0)
                                temp++;
                            else
                                break;
                        }
 
                        if (temp < N) {
                            if (arr[temp + 1][c] == val && check[temp + 1][c] == 0)
                            {
                                answer = max(answer, 2 * val);
                                arr[temp + 1][c] *= 2;
                                check[temp + 1][c] = 1;
                            }
                            else
                                arr[temp][c] = val;
                        }
                        else {
                            arr[temp][c] = val;
                        }
                    }
                }
            }
        }
        // MOVE LEFT
        else if (i == 2) {
            for (int r = 1; r <= N; r++) {
                for (int c = 1; c <= N; c++) {
                    if (arr[r][c] != 0) {
                        int temp = c;
                        val = arr[r][temp];
                        arr[r][temp] = 0;
 
                        while (temp > 1) {
                            if (arr[r][temp - 1] == 0)
                                temp--;
                            else
                                break;
                        }
 
                        if (temp > 1) {
                            if (arr[r][temp - 1] == val && check[r][temp - 1] == 0)
                            {
                                answer = max(answer, 2 * val);
                                arr[r][temp - 1] *= 2;
                                check[r][temp - 1] = 1;
                            }
                            else
                                arr[r][temp] = val;
                        }
                        else {
                            arr[r][temp] = val;
                        }
                    }
                }
            }
        }
        // MOVE RIGHT
        else if (i == 3) {
            for (int r = 1; r <= N; r++) {
                for (int c = N; c >= 1; c--) {
                    if (arr[r][c] != 0) {
                        int temp = c;
                        val = arr[r][c];
                        arr[r][c] = 0;
 
                        while (temp < N) {
                            if (arr[r][temp + 1] == 0)
                                temp++;
                            else
                                break;
                        }
 
                        if (temp < N) {
                            if (arr[r][temp + 1] == val && check[r][temp + 1] == 0)
                            {
                                answer = max(answer, 2 * val);
                                arr[r][temp + 1] *= 2;
                                check[r][temp + 1] = 1;
                            }
                            else
                                arr[r][temp] = val;
                        }
                        else {
                            arr[r][temp] = val;
                        }
                    }
                }
            }
        }
        dfs(n + 1);
        memcpy(arr, tmp, sizeof(tmp));
    }
 
    return;
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            answer = max(answer, arr[i][j]);
        }
    }
 
    dfs(0); 
 
    cout << answer << endl;
    return 0;
}