[백준] 12100, 2048 (Easy) Java

12100, 2048 (Easy)

이 문제의 board 크기는 최대 20*20, 이동 횟수는 5번이며 이동 방법은 4가지 이다.

총 4^5 가지의 이동이 가능하며, 1024 가지의 이동이 가능하다.

따라서 완전 탐색을 하더라도 약 400*1024 정도의 시간이 걸릴것이라 예상되므로 나는 완전 탐색으로 이 문제를 풀려고 했다.

이동할 수 있는 경우의 수는 dfs로 만들어 depth가 5가 되면 최대 값을 계산하고 종료하도록 하고 5 미만이라면 up,down,left,right를 모두 수행하도록 했다.

이 문제에서 주의해야할 점은,

3
2 0 0
2 0 0
4 0 0

과 같이 주어졌을때, up 을 하면

8 0 0

이 아닌,

4 0 0
4 0 0

이 나와야했다.

따라서 블록을 합친다면 처리를 해줘 다음 블록이 이미 합쳐진 블록에 합쳐지지 않게 해줘야한다.

그리고 배열 참조와 관련된 문제가 날 괴롭혔다.

이동을 수행하기 전 전달 받은 board를 left 함수로 이동시킨다면 전달 받은 board의 상태가 바뀌기 때문에 이후 다른 이동을 시킬 때 정확한 값이 나오지 않게 된다.

따라서 이동을 수행하기 전, 전달 받은 배열의 복사본을 전달해줘 이동시킬 필요가 있고,
나는 이동을 할 때 마다 매번 복사본을 전달해 이 문제를 해결하였다.

import java.util.*;
import java.io.*;

public class Main {
    static int answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int board[][] = new int[n][n];
        answer = 0;
        for (int i = 0; i < n; i++) {
            String[] in = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(in[j]);
            }
        }
        dfs(0, board);
        System.out.println(answer);
    }

    static void dfs(int cnt, int[][] board) {
        if (cnt == 5) {
            answer = Math.max(answer, find_max(board));
            return;
        }

        move_up(cnt, copy_arr(board));
        move_down(cnt, copy_arr(board));
        move_left(cnt, copy_arr(board));
        move_right(cnt, copy_arr(board));

    }

    static int[][] copy_arr(int[][] board) {
        int[][] arr = new int[board.length][board.length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                arr[i][j] = board[i][j];
            }
        }
        return arr;
    }

    static void move_up(int cnt, int[][] board) {
        for (int i = 0; i < board.length; i++) {
            int row = 0;
            int block = 0;
            for (int j = 0; j < board.length; j++) {
                if (board[j][i] != 0) {
                    if (block == board[j][i]) {
                        board[row - 1][i] = block * 2;
                        block = 0;
                        board[j][i] = 0;
                    } else {
                        block = board[j][i];
                        board[j][i] = 0;
                        board[row][i] = block;
                        row++;
                    }
                }
            }
        }
        dfs(cnt + 1, board);
    }

    static void move_down(int cnt, int[][] board) {
        for (int i = 0; i < board.length; i++) {
            int row = board.length - 1;
            int block = 0;
            for (int j = board.length - 1; j >= 0; j--) {
                if (board[j][i] != 0) {
                    if (block == board[j][i]) {
                        board[row + 1][i] = block * 2;
                        block = 0;
                        board[j][i] = 0;
                    } else {
                        block = board[j][i];
                        board[j][i] = 0;
                        board[row][i] = block;
                        row--;
                    }
                }
            }
        }
        dfs(cnt + 1, board);
    }

    static void move_left(int cnt, int[][] board) {
        for (int i = 0; i < board.length; i++) {
            int col = 0;
            int block = 0;
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] != 0) {
                    if (block == board[i][j]) {
                        board[i][col - 1] = block * 2;
                        block = 0;
                        board[i][j] = 0;
                    } else {
                        block = board[i][j];
                        board[i][j] = 0;
                        board[i][col] = block;
                        col++;
                    }
                }
            }
        }
        dfs(cnt + 1, board);
    }

    static void move_right(int cnt, int[][] board) {
        for (int i = 0; i < board.length; i++) {
            int col = board.length - 1;
            int block = 0;
            for (int j = board.length - 1; j >= 0; j--) {
                if (board[i][j] != 0) {
                    if (block == board[i][j]) {
                        board[i][col + 1] = block * 2;
                        block = 0;
                        board[i][j] = 0;
                    } else {
                        block = board[i][j];
                        board[i][j] = 0;
                        board[i][col] = block;
                        col--;
                    }
                }
            }
        }
        dfs(cnt + 1, board);
    }

    static boolean isEqual(int a, int b) {
        return a == b;
    }

    static int find_max(int[][] board) {
        int max = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                max = Math.max(max, board[i][j]);
            }
        }
        return max;
    }
}