[백준 *Java] - 2048(Easy)(12100)

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

12100번: 2048 (Easy)

문제는 사진이 많아서, 따로 블로그에 적지 않겠습니다.

---

👇 접근방식

문제를 보았을 때, 사방 탐색 문제라는 걸 알았습니다.
dfs 또는 bfs 문제인데, 일단 최소가아니라 depth(5)가 정해져있으니, dfs 로 문제를 풀어야겠다고 생각했습니다.
일단 생각으론 NxN 칸을 매 번 이동 시켰을 시, 기억을 해주어야하며? 그리고 이동했던 방향까지 기억을 해야한다고 생각하니 생각볻 복잡하게 되고, 메모리 복잡도 효율이 좋지 않을 거 같아 다른 접근방법을 고민했습니다.
그리고, dfs 로 재귀를 돌려도 depth 가 5이니 4의 5승으로 최대 1300~1400정도의 횟수만을 가지고 문제를 풀어나갈 수 있다고 생각을 했습니다. 따라서 방문처리는 하지 않은 방식으로 설계합니다.
정리를 하자면, 이번 문제의 flow는
매 움직임마다 dfs를 돌릴 때, board를 재정의하는 방식으로 구현합니다.
여기서 중요한건, idx 관리를 하는 부분과 기우는 방향을 기준으로 반대로 탐색하기를 기억해주면 됩니다.

 

아래는 코드 구현한 것입니다.

package dfs;

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

public class Main {
    static int N;
    static int max = Integer.MIN_VALUE;
    static int[][] board;
    static final int fourDirection = 4;

    static void dfs(int depth, int[][] board) {

        if (depth == 5) {
            return;
        }

        // 사방 탐색
        for (int direction  = 0; direction < fourDirection; direction++) {
            int[][] moved = changeThePositionOfNumberBoard(direction, board);
            dfs(depth + 1, moved);
        }
    }

    private static int[][] changeThePositionOfNumberBoard(int direction, int[][] board) {
        int[][] tempBoard = new int[N][N];

        switch (direction) {
            // 북쪽
            case 0 :
                // 위에서 아래로 탐색
                for (int col = 0; col < N; col++) {
                    int beforeValue = -1;
                    int index = 0;
                    for (int row = 0; row < N; row++) {
                        if (board[row][col] == 0) continue; // 빈 칸일 시 pass
                        else {
                            // 이전 값과 동일 했을 시? 값을 합치기(*2)
                            if (beforeValue == board[row][col]) {
                                int calc = board[row][col] * 2;
                                tempBoard[index - 1][col] = calc;
                                max = Math.max(max, calc);
                                beforeValue = -1;
                            // 그게 아닐 시? index 에 맞춰서 값을 넣어줍니다.
                            }else {
                                tempBoard[index++][col] = board[row][col];
                                beforeValue = board[row][col];
                            }
                        }
                    }
                }
                break;
            // 동쪽
            case 1 :
                // 우(오른쪽)에서 좌(왼쪽)으로 탐색
                for (int row = 0; row < N; row++) {
                    int beforeValue = -1;
                    int index = N - 1;
                    for (int col = N - 1; col >= 0; col--) {
                        if (board[row][col] == 0) continue; // 빈 칸일 시 pass
                        else {
                            // 이전 값과 동일 했을 시? 값을 합치기(*2)
                            if (beforeValue == board[row][col]) {
                                int calc = board[row][col] * 2;
                                tempBoard[row][index + 1] = calc;
                                max = Math.max(max, calc);
                                beforeValue = -1;
                            // 그게 아닐 시? index 에 맞춰서 값을 넣어줍니다.
                            }else {
                                tempBoard[row][index--] = board[row][col];
                                beforeValue = board[row][col];
                            }
                        }
                    }
                }
                break;
            // 남쪽
            case 2 :
                // 아래에서 위로 탐색
                for (int col = 0; col < N; col++) {
                    int beforeValue = -1;
                    int index = N - 1;
                    for (int row = N - 1; row >= 0; row--) {
                        if (board[row][col] == 0) continue; // 빈 칸일 시 pass
                        else {
                            // 이전 값과 동일 했을 시? 값을 합치기(*2)
                            if (beforeValue == board[row][col]) {
                                int calc = board[row][col] * 2;
                                tempBoard[index + 1][col] = calc;
                                max = Math.max(max, calc);
                                beforeValue = -1;
                            // 그게 아닐 시? index 에 맞춰서 값을 넣어줍니다.
                            }else {
                                tempBoard[index--][col] = board[row][col];
                                beforeValue = board[row][col];
                            }
                        }
                    }
                }
                break;
            // 서쪽
            case 3 :
                // 좌(왼쪽)에서 우(오른쪽)으로 탐색
                for (int row = 0; row < N; row++) {
                    int beforeValue = -1;
                    int index = 0;
                    for (int col = 0; col < N; col++) {
                        if (board[row][col] == 0) continue; // 빈 칸일 시 pass
                        else {
                            // 이전 값과 동일 했을 시? 값을 합치기(*2)
                            if (beforeValue == board[row][col]) {
                                int calc = board[row][col] * 2;
                                tempBoard[row][index - 1] = calc;
                                max = Math.max(max, calc);
                                beforeValue = -1;
                                // 그게 아닐 시? index 에 맞춰서 값을 넣어줍니다.
                            }else {
                                tempBoard[row][index++] = board[row][col];
                                beforeValue = board[row][col];
                            }
                        }
                    }
                }
                break;
        }

        return tempBoard;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        for (int row = 0; row < N; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int column = 0; column < N; column++) {
                board[row][column] = Integer.parseInt(st.nextToken());
                max = Math.max(max, board[row][column]);
            }
        }

        dfs(0, board);
        System.out.println(max);
    }
}