2048 (Easy)

이 문제는 2048 게임을 구현하는 문제입니다. 이 문제를 풀 때, 새겨둬야 할 조건이 있는데요. 바로 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. 라는 부분입니다.

(저는 개인적으로 이 조건을 놓쳐서 틀렸었습니다...)

보드의 최대 크기는 20x20이고, 최대 5번 이동했을 때의 최댓값을 구하라고 했습니다. 방향은 상하좌우 4방향이 존재하고, 5번 이동할 수 있으므로 상태의 최대 갯수는 4^5인 1,024임을 알 수 있습니다.

그리고 각 보드에서 블록을 옮기는 비용은, 보드의 크기(400)에 각 보드를 한 방향으로 옮기는 비용인 20이므로, 넉넉히 잡아서 각 블록을 끝방향으로 몰아가는 비용인 400*20 = 8,000 정도 된다고 볼 수 있습니다.

그리고 상태의 최대 갯수는 1,024 이므로 넉넉 잡아서 10,000,000의 루프가 돌 수 있다고 생각할 수 있습니다. 물론 구현하다보면 현재 보드의 상태를 복사해야 되는 상황도 있겠지만, 그럼에도 브루트포스로 제한 시간 내에는 가능할 것이라고 예측할 수 있습니다.

풀이1

구현문제는 문제의 조건을 그냥 그대로 구현하면 됩니다.

Board를 나타내는 클래스를 선언하고, 해당 Board를 4방향으로 움직일 수 있게끔 메서드를 정의하고, 최대 5번 이동할 수 있다고 했으니, Board가 자신의 상태를 복사해서 다른 방향으로 움직일 수 있도록 하면 됩니다.

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

public class Main {
    private static final int[] UP = {-1, 0};
    private static final int[] RIGHT = {0, 1};
    private static final int[] DOWN = {1, 0};
    private static final int[] LEFT = {0, -1};

    private static int N;
    private static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws Throwable {
        Board board = input();

        move(board, 5);

        System.out.println(ans);
    }

    private static Board input() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        N = Integer.parseInt(br.readLine());

        final int[][] board = new int[N][N];

        for (int ni = 0; ni < N; ni++) {
            final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int nj = 0; nj < N; nj++) {
                board[ni][nj] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();

        return new Board(board);
    }

    private static void move(Board board, int remain) {
        if (remain == 0) {
            return;
        }

        final int nextRemain = remain - 1;

        move(board.up(), nextRemain);
        move(board.right(), nextRemain);
        move(board.down(), nextRemain);
        move(board.left(), nextRemain);
    }

    static class Board {
        private final int[][] board;

        public Board(int[][] board) {
            this.board = board;
        }

        public Board up() {
            return copy().moveUp();
        }

        private Board moveUp() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveBlock(UP, y, x);
                }
            }

            return this;
        }

        public Board down() {
            return copy().moveDown();
        }

        private Board moveDown() {
            for (int y = N-1; y >= 0; y--) {
                for (int x = 0; x < N; x++) {
                    moveBlock(DOWN, y, x);
                }
            }

            return this;
        }

        public Board left() {
            return copy().moveLeft();
        }

        private Board moveLeft() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveBlock(LEFT, y, x);
                }
            }

            return this;
        }

        public Board right() {
            return copy().moveRight();
        }

        private Board moveRight() {
            for (int y = 0; y < N; y++) {
                for (int x = N-1; x >= 0; x--) {
                    moveBlock(RIGHT, y, x);
                }
            }

            return this;
        }

        private Board copy() {
            final int[][] newBoard = new int[N][N];

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    newBoard[y][x] = Math.abs(board[y][x]);
                }
            }

            return new Board(newBoard);
        }

        /**
         * y, x 블록을 dir 방향으로 민다.
         *
         * @param dir 방향
         * @param y y좌표
         * @param x x좌표
         */
        private void moveBlock(int[] dir, int y, int x) {
            if (board[y][x] == 0) {
                return;
            }

            while (true) {
                int nextY = y + dir[0];
                int nextX = x + dir[1];

                if (isOutOfIndex(nextY, nextX)) {
                    break;
                }

                final int current = board[y][x];
                final int next = board[nextY][nextX];

                // 해당 방향이 비어있다면
                // 그 위치로 민다.
                if (next == 0) {
                    board[nextY][nextX] = board[y][x];
                    board[y][x] = 0;

                    y = nextY;
                    x = nextX;

                    continue;
                }

                // 해당 방향이 같은 블럭이면
                // 합친다.
                // 이미 합쳐진 블록이면 더이상 합치지 않는다.
                // 해당 값은 음수로 표현한다.
                if (next == current && next > 0) {
                    board[y][x] = 0;
                    board[nextY][nextX] *= -2;

                    y = nextY;
                    x = nextX;

                    break;
                }

                // 다른 블럭이 있는 경우이므로
                // 끝낸다.
                break;
            }

            // 합쳐진 블록의 값을 음수로 체크했으므로, 절댓값으로 표시한다.
            ans = Math.max(ans, Math.abs(board[y][x]));
        }

        private boolean isOutOfIndex(int y, int x) {
            return y < 0 || y >= N || x < 0 || x >= N;
        }
    }
}

moveBlock 메서드를 이용하여 문제를 풀면 되는데, 이 때 이미 합쳐진 블록의 경우 음수를 이용하여 표시하였습니다.

풀이2

풀이1에서는 4방향을 각각 구현했는데, 보드판 자체를 90도씩 회전시키고 무조건 위로 합쳐지게만 만들어도 결국 같습니다. 이런 아이디어를 구현한 코드는 아래와 같습니다.

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

public class Main {
    private static int N;
    private static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws Throwable {
        Board board = input();

        move(board, 5);

        System.out.println(ans);
    }

    private static Board input() throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        N = Integer.parseInt(br.readLine());

        final int[][] board = new int[N][N];

        for (int ni = 0; ni < N; ni++) {
            final StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int nj = 0; nj < N; nj++) {
                board[ni][nj] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();

        return new Board(board);
    }

    private static void move(Board board, int remain) {
        if (remain == 0) {
            return;
        }

        final int nextRemain = remain - 1;

        Board next = board;
        for (int i = 0; i < 4; i++) {
            next = next.rotate();
            move(next.copy().up(), nextRemain);
        }
    }

    static class Board {
        private final int[][] board;

        public Board(int[][] board) {
            this.board = board;
        }

        public Board rotate() {
            final int[][] newBoard = new int[N][N];

            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    // 회전할 때에는 절댓값을 씌워줘서 기존에 합쳐졌다는 표시가 남은 블록을
                    // 제거해줘야 한다.
                    newBoard[y][x] = Math.abs(board[N - x - 1][y]);
                }
            }

            return new Board(newBoard);
        }

        public Board up() {
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    moveUp(y, x);
                }
            }

            return this;
        }

        public Board copy() {
            final int[][] copied = new int[N][N];
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    copied[y][x] = board[y][x];
                }
            }

            return new Board(copied);
        }

        /**
         * y, x 블록을 윗쪽 방향으로 민다.
         *
         * @param y y좌표
         * @param x x좌표
         */
        private void moveUp(int y, int x) {
            if (board[y][x] == 0) {
                return;
            }

            while (true) {
                int nextY = y - 1;
                int nextX = x;

                if (isOutOfIndex(nextY, nextX)) {
                    break;
                }

                final int current = board[y][x];
                final int next = board[nextY][nextX];

                // 해당 방향이 비어있다면
                // 그 위치로 민다.
                if (next == 0) {
                    board[nextY][nextX] = board[y][x];
                    board[y][x] = 0;

                    y = nextY;
                    x = nextX;

                    continue;
                }

                // 해당 방향이 같은 블럭이면
                // 합친다.
                // 이미 합쳐진 블록이면 더이상 합치지 않는다.
                // 해당 값은 음수로 표현한다.
                if (next == current && next > 0) {
                    board[y][x] = 0;
                    board[nextY][nextX] *= -2;

                    y = nextY;
                    x = nextX;

                    break;
                }

                // 다른 블럭이 있는 경우이므로
                // 끝낸다.
                break;
            }

            // 합쳐진 블록의 값을 음수로 체크했으므로, 절댓값으로 표시한다.
            ans = Math.max(ans, Math.abs(board[y][x]));
        }

        private boolean isOutOfIndex(int y, int x) {
            return y < 0 || y >= N || x < 0 || x >= N;
        }
    }
}

거의 모든 코드가 같지만, rotate를 추가하고 4방향으로 옮기는 대신 무조건 윗쪽 방향으로만 옮기도록 했습니다.