BOJ 12100 - 2048

https://www.acmicpc.net/problem/12100

 

보드판 내의 전체 블록이 함께 이동한다. 이동 방향은 상, 하, 좌, 우이다.

이때 같은 값을 갖는 두 블록이 충돌하면 두 블록은 합쳐지게 된다.

단, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.

NxN 크기의 보드판에서 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값

보드판의 상태 관리가 필요하다.

각 블록을 관리를 할 텐데 해당 블록에는 값, 보드판에서의 위치, 그리고 이미 합쳐진 상태인지의 상태가 필요하다.

이동 방향 또한 중요한데 예를 들어 같은 값이 3개가 같은 열에 존재한다고 하자. 이 때 위쪽으로 이동하는 경우 위의 2개가 합쳐진다. 즉 위쪽에 가까운 것들이 먼저 합쳐진다.

또한 이동 횟수의 최댓값이 5로 정해져 있다.

 

백트랙킹 방법을 쓰면 될 것 같다.

백트랙킹의 탈출 조건이 뭘까 이동 횟수가 탈출 조건이 될 것이다. 이동 횟수가 5가 되면 최댓값을 갱신하고 탈출하면 된다.

또한 방문 처리를 해야 불필요한 반복을 하지 않는다. 하지만 이 방문을 어떤 기준으로 해야 할까?

그렇지만 이 방문 처리는 블록 내에 존재하는 모든 블록들을 통해 해야만 한다. N이 커질수록 블록의 개수가 NxN개가 되므로 곤란해진다.

최대 이동 횟수가 5회이기 때문에 방문처리를 안 하는 것도 방법일 수 있겠다.

그런데 블록을 어떻게 움직일 것인가.

1. 그냥 각각의 블록들을 독립적으로 이동시켜 Queue에 쌓는다.
2. 해당 Queue를 이동 거리에 따라 정렬한다.
3. 앞에서부터 꺼낸다.
4. 꺼내면서 값이 같으면 합치고 합쳐진 상태를 이전 것으로 기록한다.
5. 다음 것을 꺼냈는데 이전 것과 같다면 이전것과 비교를 통해 합치거나 위치를 재정렬한다.

그런데 이 방법은 위치 조정이 복잡해질 것 같다. 또한 이전 블록과 비교해야 하는데 이거는 이동 방향에 따라 같은 열, 같은 행 등을 관리해줘야 한다.

따라서 그냥 블록을 이동방향에 따라 정렬하고 새로운 보드를 만들어 이동방향의 경계에 가까운 순서대로 배치해 나가자.

그런데 보드의 상태를 관리하는 클래스 내부에 보드판을 어떤 자료구조로 가지고 있어야 할까?

Block [][]과 int [][]의 선택지가 있다. Block의 경우 해당 위치에 블록의 병합 여부를 판단하기 쉬워지지만 객체를 제어해야 한다는 점에서 불편함이 늘어난다.

실수의 여지를 줄이기 위해 Block에서 병합 여부를 분리하고 별도의 boolean [][]을 사용해 관리하겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Test {

    static FastReader scan = new FastReader();
    static int N;
    static int[][] grid;
    static int maxValue = Integer.MIN_VALUE;
    static final int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 보드판의 상태
    static class Board {
        final int[][] board;
        final List<Block> blocks;
        final int maxValue;
        final int moveCount;

        public Board(int[][] board, List<Block> blocks, int maxValue, int moveCount) {
            this.board = board;
            this.blocks = blocks;
            this.maxValue = maxValue;
            this.moveCount = moveCount;
        }

        void printBoard(int[][] board) {
            for (int[] row : board) {
                System.out.println(Arrays.toString(row));
            }
            System.out.println();
        }

        Board move(int dir) {
            //이동 방향을 전달받아 현재 보드판의 상태를 보고 이동시킨 후 새로운 보드판을 리턴
            int[][] newBoard = new int[N][N];
            boolean[][] merged = new boolean[N][N];

            List<Block> sortedBlock = sortedBlockByDir(this.blocks, dir);

            for (Block block : sortedBlock) {
                Block movedBlock = moveBlock(block, dir, newBoard);
                int r = movedBlock.r;
                int c = movedBlock.c;
                int value = movedBlock.value;
                if (newBoard[r][c] != 0) {
                    // 이미 존재한다.
                    if (newBoard[r][c] == value && !merged[r][c]) {
                        // 값이 같은데 아직 병합이 안된 칸
                        newBoard[r][c] = value * 2;
                        merged[r][c] = true;
                    } else {
                        // 값이 다르거나 병합이 이미 됐거나 -> 위치 조정
                        newBoard[r - DIRECTION[dir][0]][c - DIRECTION[dir][1]] = value;
                    }
                } else {
                    // 빈 공간
                    newBoard[r][c] = value;
                }
            }
//            printBoard(newBoard);
            // 새로운 보드가 완성된 상태
            List<Block> newBlocks = new ArrayList<>();
            int maxValue = this.maxValue;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (newBoard[i][j] == 0) {
                        continue;
                    }
                    maxValue = Math.max(maxValue, newBoard[i][j]);
                    Block block = new Block(i, j, newBoard[i][j]);
                    newBlocks.add(block);
                }
            }

            return new Board(newBoard, newBlocks, maxValue, moveCount + 1);
        }

        private Block moveBlock(Block block, int dir, int[][] board) {
            int r = block.r;
            int c = block.c;

            while (isValidPosition(r + DIRECTION[dir][0], c + DIRECTION[dir][1]) && board[r][c] == 0) {
                r += DIRECTION[dir][0];
                c += DIRECTION[dir][1];
            }

            return new Block(r, c, block.value);
        }

        private List<Block> sortedBlockByDir(List<Block> blocks, int dir) {
            if (dir == 0) {
                // 상 -> r오름차순
                return blocks.stream().sorted(Comparator.comparingInt(block -> block.r)).collect(Collectors.toList());
            } else if (dir == 1) {
                // 하 -> r내림차순
                return blocks.stream().sorted(Comparator.comparingInt(block -> -block.r)).collect(Collectors.toList());
            } else if (dir == 2) {
                // 좌 -> c오름차순
                return blocks.stream().sorted(Comparator.comparingInt(block -> block.c)).collect(Collectors.toList());
            } else {
                // 우 -> c내림차순
                return blocks.stream().sorted(Comparator.comparingInt(block -> -block.c)).collect(Collectors.toList());
            }
        }

        private boolean isValidPosition(int r, int c) {
            return r >= 0 && r < N && c >= 0 && c < N;
        }
    }

    // 보드판 내 블록
    static class Block {
        final int r;
        final int c;
        final int value;

        public Block(int r, int c, int value) {
            this.r = r;
            this.c = c;
            this.value = value;
        }
    }

    static void dfs(Board board) {
        if (board.moveCount >= 5) {
            maxValue = Math.max(maxValue, board.maxValue);
            return;
        }

        for (int dir = 0; dir < 4; dir++) {
            dfs(board.move(dir));
        }
    }

    static void input() {
        N = scan.nextInt();
        grid = new int[N][N];
    }

    public static void main(String[] args) {
        input();
        List<Block> blocks = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = scan.nextInt();
                if (grid[i][j] == 0) {
                    continue;
                }
                maxValue = Math.max(grid[i][j], maxValue);
                blocks.add(new Block(i, j, grid[i][j]));
            }
        }

        Board board = new Board(grid, blocks, maxValue, 0);
        dfs(board);

        System.out.println(maxValue);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}