아이디어

• 2048 게임의 조작을 구현한다.
  • 위로 이동하는 경우를 생각해보자. 나머지도 방향만 다르게 하면 된다.
    1. 우선 맨 위부터 빈 공간이 아닌 숫자가 있는지 탐색한다.
    2. 숫자가 있으면 천장이나 다른 숫자에 닿을 때까지 위로 끌어 올린다.
    3. 만약 끌어올린 후 위가 천장이 아니고, 위 숫자와 같을 경우에는 위의 숫자에 합친다.
  • 이러한 방식은 동시에 숫자가 2번 이상 병합이 될 수 있다는 문제가 있다. (예: [2, 2, 4, 8] → [16])
  • 따라서 1번의 병합 이후에는, 마지막으로 병합한 위치까지만 끌어올릴 수 있도록 해야 한다.
• 위, 아래, 왼쪽, 오른쪽 이동을 5번 나열하는 $4^5$가지 경우의 수를 완전탐색한다.
  • binary counting을 응용한다.
  • bitmask의 i번 비트가 1인지의 여부를 mask & 1 << i != 0로도 구할 수 있지만, 반대로 mask를 움직여 mask >> i & 1 == 1과 같이 쓸 수도 있다. 이 방법은 mask >> i & 1의 값이 1 또는 0으로 나온다는 추가적인 특징이 있다.
  • 위 특징을 확장해 비트를 2개씩 읽을 수 있다. 그렇게 읽은 2자리 이진수(0~3)로 방향을 나타낼 것이다.

    int dir = mask >> (2*j) & 0b11;  // for j s.t. 0 <= j < 5

  • $4^5$는 $2^{10}$이므로 $0$부터 $2^{10}-1$까지 반복하면 된다.
  • 이를 통해 네 방향의 5번 조작에 대한 모든 중복순열을 탐색할 수 있다.
• 5번 이동에 대한 한 번의 경우가 끝나면 최댓값을 확인해서 답안을 갱신하고, 보드를 초기 상태로 되돌린다.
• 범위: 혹시 모르니 long으로 썼다. 사실 int여도 상관 없는 문제다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int N;
    static long[][] map, ori;

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(rd.readLine());
        ori = new long[N][N];
        map = new long[N][N];

        for (int y=0; y<N; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<N; x++) {
                ori[y][x] = Integer.parseInt(tk.nextToken());
            }
        }

        long ans = 0;
        for (int mask=0; mask < (1 << (2 * 5)); mask++) {
            resetMap();
            for (int j=0; j<5; j++) {
                int d = mask >> (2 * j) & 0b11;
                switch (d) {
                    case 0: moveUp(); break;
                    case 1: moveRight(); break;
                    case 2: moveDown(); break;
                    default: moveLeft(); break;
                }
            }
            ans = Math.max(ans, getMaxValue());
        }
        System.out.println(ans);
    }

    static void moveUp() {
        for (int x=0; x<N; x++) {
            int minc = 0;
            for (int y=0; y<N; y++) {
                if (map[y][x] == 0) continue;
                int c = y;
                while (c > minc && map[c - 1][x] == 0) {
                    map[c - 1][x] = map[c][x];
                    map[c][x] = 0;
                    c--;
                }
                if (c > minc && map[c-1][x] == map[c][x]) {
                    map[c-1][x] *= 2;
                    map[c][x] = 0;
                    minc = c;
                }
            }
        }
    }

    static void moveDown() {
        for (int x=0; x<N; x++) {
            int maxc = N - 1;
            for (int y=N-1; y>=0; y--) {
                if (map[y][x] == 0) continue;
                int c = y;
                while (c < maxc && map[c + 1][x] == 0) {
                    map[c + 1][x] = map[c][x];
                    map[c][x] = 0;
                    c++;
                }
                if (c < maxc && map[c+1][x] == map[c][x]) {
                    map[c+1][x] *= 2;
                    map[c][x] = 0;
                    maxc = c;
                }
            }
        }
    }

    static void moveLeft() {
        for (int y=0; y<N; y++) {
            int minc = 0;
            for (int x=0; x<N; x++) {
                if (map[y][x] == 0) continue;
                int c = x;
                while (c > minc && map[y][c - 1] == 0) {
                    map[y][c - 1] = map[y][c];
                    map[y][c] = 0;
                    c--;
                }
                if (c > minc && map[y][c-1] == map[y][c]) {
                    map[y][c-1] *= 2;
                    map[y][c] = 0;
                    minc = c;
                }
            }
        }
    }

    static void moveRight() {
        for (int y=0; y<N; y++) {
            int maxc = N - 1;
            for (int x=N-1; x>=0; x--) {
                if (map[y][x] == 0) continue;
                int c = x;
                while (c < maxc && map[y][c + 1] == 0) {
                    map[y][c + 1] = map[y][c];
                    map[y][c] = 0;
                    c++;
                }
                if (c < maxc && map[y][c+1] == map[y][c]) {
                    map[y][c+1] *= 2;
                    map[y][c] = 0;
                    maxc = c;
                }
            }
        }
    }

    static void resetMap() {
        for (int y=0; y<N; y++) {
            for (int x=0; x<N; x++) {
                map[y][x] = ori[y][x];
            }
        }
    }

    static long getMaxValue() {
        long max = 0;
        for (int y=0; y<N; y++) {
            for (int x=0; x<N; x++) {
                max = Math.max(max, map[y][x]);
            }
        }
        return max;
    }
}

메모리 및 시간

• 메모리: 16084 KB
• 시간: 368 ms

리뷰

• 백트래킹은 쓰지 않아도 되었지만… 생각할 점이 많은 구현 문제였다.
  • 다음엔 써보자.
• 기본적으로 완전 탐색의 시점에서 풀이하고, 안되면 점진적으로 최적화를 적용한다는 생각을 가져보자.
• 구현이 빡셀 문제일수록 코드를 구조화하자.