[BOJ] #12100 2048

시간 제한	메모리 제한	정답 비율
1 초	512 MB	23.670%

12100번: 2048 (Easy)

 

문제

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

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

 

해결

key point, N의 크기가 20이므로 완전탐색한다.

• go( ) 함수를 활용하여 가능한 이동횟수 5번 동안 상하좌우 네 방향의 움직임을 모두 해본다.
  • 4 * 4 * 4 * 4 * 4 = 1024 번의 연산을 하여 가장 큰 블록을 찾는다.
• 상하좌우 네 방향에 대해서 인접한 숫자들을 비교하여 같으면 합치고
• 빈공간들을 숫자로 채울 수 있다면 채웠다.
• 숫자가 같아서 합칠 때는, chk배열을 이용해서 1 변환해줬고, chk가 0인 숫자들 끼리 합칠 수 있게 했다.

3
2 2 2
4 4 4
8 8 8
16


9
4 2 0 0 0 0 0 0 0
4 8 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
8 4 0 0 0 0 0 0 0
8 2 0 0 0 0 0 0 0
64

3
0 8 1024
4 0 4
0 1024 32
2048

3
256 8 128
16 0 256
0 8 0
512

코드

메모리	시간
1988 KB	8 ms

#include <iostream>
using namespace std;
 
int n, arr[25][25], Max;
 
void arr_copy(int a[][25], int arr[][25]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = arr[i][j];
        }
    }
}
 
void go(int arr[25][25], int d, int cnt) {
    if (cnt > 5) {
        return;
    }
 
    int a[25][25] = { 0 };
    arr_copy(a, arr);
 
    // 만들고나서 현재 가장 큰 값
    int tMax = 0, chk[25][25] = { 0 };
    if (d > -1) {
        switch (d)
        {
        case 0:  // 상
            for (int j = 0; j < n; j++) {
                int i = 0;
                while (i < n - 1) {
                    if (a[i][j]) {
                        // 당길 숫자의 위치 찾기
                        int idx = i + 1;
                        while (!a[idx][j] && idx < n) {
                            idx++;
                        }
                        if (!chk[idx][j] && a[i][j] == a[idx][j]) {
                            chk[i][j] = chk[idx][j] = 1;
                            a[i][j] *= 2;
                            a[idx][j] = 0;
                            tMax = a[i][j] > tMax ? a[i][j] : tMax;
                        }
                    }
                    i++;
                }
                // 빈공간 당기기 0이면 가장 가까운 숫자 찾아서 가져오기 
                i = 0;
                while (i < n - 1) {
                    if (!a[i][j]) {
                        // 당길 숫자의 위치 찾기
                        int idx = i + 1;
                        while (!a[idx][j] && idx < n) {
                            idx++;
                        }
                        a[i][j] = a[idx][j];
                        a[idx][j] = 0;
                    }
                    i++;
                }
            }
            break;
        case 1:  // 하
            for (int j = 0; j < n; j++) {
                int i = n - 1;
                while (i > 0) {
                    if (a[i][j]) {
                        // 당길 숫자의 위치 찾기
                        int idx = i - 1;
                        while (!a[idx][j] && idx > 0) {
                            idx--;
                        }
                        if (!chk[idx][j] && a[i][j] == a[idx][j]) {
                            chk[i][j] = chk[idx][j] = 1;
                            a[i][j] *= 2;
                            a[idx][j] = 0;
                            tMax = a[i][j] > tMax ? a[i][j] : tMax;
                        }
                    }
                    i--;
                }
                // 빈공간 당기기 0이면 가장 가까운 숫자 찾아서 가져오기
                i = n - 1;
                while (i > 0) {
                    if (!a[i][j]) {
                        // 당길 숫자의 위치 찾기
                        int idx = i - 1;
                        while (!a[idx][j] && idx > 0) {
                            idx--;
                        }
                        a[i][j] = a[idx][j];
                        a[idx][j] = 0;
                    }
                    i--;
                }
            }
            break;
        case 2:  // 좌
            for (int i = 0; i < n; i++) {
                int j = 0;
                while (j < n - 1) {
                    if (a[i][j]) {
                        int idx = j + 1;
                        while (!a[i][idx] && idx < n) {
                            idx++;
                        }
                        if (!chk[i][idx] && a[i][j] == a[i][idx]) {
                            chk[i][j] = chk[i][idx] = 1;
                            a[i][j] *= 2;
                            a[i][idx] = 0;
                            tMax = a[i][j] > tMax ? a[i][j] : tMax;
                        }
                    }
                    j++;
                }
                // 빈공간 당기기 0이면 가장 가까운 숫자 찾아서 가져오기
                j = 0;
                while (j < n - 1) {
                    if (!a[i][j]) {
                        int idx = j + 1;
                        while (!a[i][idx] && idx < n - 1) {
                            idx++;
                        }
                        a[i][j] = a[i][idx];
                        a[i][idx] = 0;
                    }
                    j++;
                }
            }
            break;
        case 3: // 우
            for (int i = 0; i < n; i++) {
                int j = n - 1;
                while (j > 0) {
                    if (a[i][j]) {
                        int idx = j - 1;
                        while (!a[i][idx] && idx > 0) {
                            idx--;
                        }
                        if (!chk[i][idx] && a[i][j] == a[i][idx]) {
                            chk[i][j] = chk[i][idx] = 1;
                            a[i][j] *= 2;
                            a[i][idx] = 0;
                            tMax = a[i][j] > tMax ? a[i][j] : tMax;
                        }
                    }
                    j--;
                }
                // 빈공간 당기기 0이면 가장 가까운 숫자 찾아서 가져오기
                j = n - 1;
                while (j > 0) {
                    if (!a[i][j]) {
                        int idx = j - 1;
                        while (!a[i][idx] && idx > 0) {
                            idx--;
                        }
                        a[i][j] = a[i][idx];
                        a[i][idx] = 0;
                    }
                    j--;
                }
            }
            break;
        }
    }
 
    Max = tMax > Max ? tMax : Max;
 
    for (int i = 0; i < 4; i++) {
        go(a, i, cnt + 1);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
            Max = arr[i][j] > Max ? arr[i][j] : Max;
        }
    }
 
    go(arr, -1, 0);
 
    printf("%d", Max);
 
    return 0;
}

 

다른 방법

// 0: down, 1: up, 2: left, 3: right
ok = false;
if (dir == 0) {
    for (int i=n-2; i>=0; i--) {
        for (int j=0; j<n; j++) {
            if (d[i][j].first == 0) continue;
            if (d[i+1][j].first == 0) {
                d[i+1][j].first = d[i][j].first;
                d[i+1][j].second = d[i][j].second;
                d[i][j].first = 0;
                ok = true;
            } else if (d[i+1][j].first == d[i][j].first) {
                if (d[i][j].second == false && d[i+1][j].second == false) {
                    d[i+1][j].first *= 2;
                    d[i+1][j].second = true;
                    d[i][j].first = 0;
                    ok = true;
                }
            }
        }
    }
}

위의 코드처럼 if 문으로 숫자를 합치는 것과 동시에 공백을 채우는 방법도 있다.

 

더 좋은 방법

key point, 매회 회전시키고 연산을 하다보면, 네 방향에 대한 연산을 모두 하게 된다.

• 연산은 up( ) 메소드로 한다.
• 새로운 dfs함수를 호출하기 전에 90도 회전한다. → r90( )

메모리	시간
1112 KB	4 ms

#include<stdio.h>
#include<memory.h>
 
int ans, N, i, j;
struct board {
    int t[20][20];
    void r90() {
        int t2[20][20];
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                t2[i][j] = t[N - j - 1][i];
            }
        }
        memcpy(t, t2, sizeof(t));
    }
    void up() {
        int t2[20][20];
        for (i = 0; i < N; i++) {
            int c = -1, d = 0;
            for (j = 0; j < N; j++) {
                if (t[i][j] == 0);
                else if (d && t[i][j] == t2[i][c]) t2[i][c] *= 2, d = 0;
                else t2[i][++c] = t[i][j], d = 1;
            }
            for (c++; c < N; c++) t2[i][c] = 0;
        }
        memcpy(t, t2, sizeof(t));
    }
    void max_value() {
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if (ans < t[i][j]) ans = t[i][j];
            }
        }
    }
};
 
void dfs(board c, int l)
{
    if (l >= 5) {
        c.max_value();
        return;
    }
    for (int i = 0; i < 4; i++) {
        board d = c;
        d.up();
        dfs(d, l + 1);
        c.r90();
    }
}
 
int main()
{
    board c;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) scanf("%d", c.t[i] + j);
    }
    dfs(c, 0);
    printf("%d\n", ans);
}

up( )

up메소드에서는 t2라는 새로운 배열을 선언하고, c 라는 인자로 0을 제외한 숫자들을 차례대로 쌓을 수 있게 한다.

변수 d는 숫자를 합칠 때 바로 앞 뒤(c, j)에 존재하는 숫자끼리 합치는 방법밖에 없기 때문에, 바로 인접한 위치에 있는 숫자와 합치고나면 d를 0으로 바꿔 (c+1, j+1)의 값이 같더라도 d가 0이므로 합치지 않고 넘어간다.

t1의 i행의 모든 열을 탐색했다면 나머지 부분에는 0을 채우고, t에 t2의 내용을 복사한다.

r90( )

마찬가지로 t2배열을 만들어서 t를 90도 회전한 값으로 채운다.

위의 코드처럼 t2를 0부터 n까지 순차적으로 채우고 싶다면, 해당 위치에서 반시계방향으로 90도 회전한 위치에 있는 t의 값을 넣어줘야한다. 그래야 t배열을 시계방향으로 90도 회전한 값이 t2가 된다.

t2를 모두 구했다면 t에 다시 복사하며 종료한다.

max_value( )

가장 큰 블록의 값을 출력한다.