BOJ_12100 : 2048 (Easy)

👉 문제링크

12100번: 2048 (Easy)

---

🔸 문제 분석 🔸

• N x N 게임 판에서 2048을 수행한다.
• 5번 수행했을 때 최대값을 출력한다.

🔸 문제 풀이 🔸

• 2048게임 규칙에 따라 구현하면 되는 문제이다.
  
  • 이동 방향에 따라 모든 칸의 숫자가 이동한다.
  • 같은 숫자는 합쳐지고, 같은 회차에서 더이상 합쳐지지 않는다.
  • 먼저 움직인 숫자가 먼저 합쳐진다.
• 최대값을 찾기위해 5회 게임 횟수의 모든 경우의 수를 확인한다.
  • 풀이는 DFS로 탐색하였다.

🔸 코드 🔸

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

public class Main {
    private static final int MAX = 5; // 최대 이동 수
    private static int N, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        answer = 0;
        play_2048(0, map);

        bw.write(Integer.toString(answer));
        bw.flush();
    }

    private static void play_2048(int cnt, int[][] map) {
//        print(map);
        if (cnt == MAX) {
            get_maxVal(map);
            return;
        }

//        System.out.println("up : " + (cnt + 1));
        play_2048(cnt + 1, move_up(copyMap(map), new boolean[N][N]));
//        System.out.println("down : " + (cnt + 1));
        play_2048(cnt + 1, move_down(copyMap(map), new boolean[N][N]));
//        System.out.println("left : " + (cnt + 1));
        play_2048(cnt + 1, move_left(copyMap(map), new boolean[N][N]));
//        System.out.println("right : " + (cnt + 1));
        play_2048(cnt + 1, move_right(copyMap(map), new boolean[N][N]));
    }


    private static int[][] move_up(int[][] map, boolean[][] flag) {
        for (int col = 0; col < N; col++) {
            for (int row = 1; row < N; row++) {

                int next = row;
                while (next - 1 >= 0 && !flag[next - 1][col]) {
                    if (map[next - 1][col] == 0)
                        next--;
                    else if (map[next - 1][col] == map[row][col]) {
                        next--;
                        break;
                    } else
                        break;
                }

                if (next != row && !flag[next][col]) {
                    if (map[next][col] == 0) { // 단순 이동
                        map[next][col] = map[row][col];
                        map[row][col] = 0;
                    } else if (map[next][col] == map[row][col]) { // 합치기
                        map[next][col] *= 2;
                        map[row][col] = 0;
                        flag[next][col] = true;
                    }
                }
            }
        }

        return map;
    }

    private static int[][] move_down(int[][] map, boolean[][] flag) {
        for (int col = 0; col < N; col++) {
            for (int row = N - 2; row >= 0; row--) {

                int next = row;
                while (next + 1 < N && !flag[next + 1][col]) {
                    if (map[next + 1][col] == 0)
                        next++;
                    else if (map[next + 1][col] == map[row][col]) {
                        next++;
                        break;
                    } else
                        break;
                }

                if (next != row && !flag[next][col]) {
                    if (map[next][col] == 0) { // 단순 이동
                        map[next][col] = map[row][col];
                        map[row][col] = 0;
                    } else if (map[next][col] == map[row][col]) { // 합치기
                        map[next][col] *= 2;
                        map[row][col] = 0;
                        flag[next][col] = true;
                    }
                }
            }
        }

        return map;
    }

    private static int[][] move_left(int[][] map, boolean[][] flag) {
        for (int row = 0; row < N; row++) {
            for (int col = 1; col < N; col++) {

                int next = col;
                while (next - 1 >= 0 && !flag[row][next - 1]) {
                    if (map[row][next - 1] == 0)
                        next--;
                    else if (map[row][next - 1] == map[row][col]) {
                        next--;
                        break;
                    } else
                        break;
                }

                if (next != col && !flag[row][next]) {
                    if (map[row][next] == 0) { // 단순 이동
                        map[row][next] = map[row][col];
                        map[row][col] = 0;
                    } else if (map[row][next] == map[row][col]) { // 합치기
                        map[row][next] *= 2;
                        map[row][col] = 0;
                        flag[row][next] = true;
                    }
                }
            }
        }

        return map;
    }

    private static int[][] move_right(int[][] map, boolean[][] flag) {
        for (int row = 0; row < N; row++) {
            for (int col = N - 2; col >= 0; col--) {

                int next = col;
                while (next + 1 < N && !flag[row][next + 1]) {
                    if (map[row][next + 1] == 0)
                        next++;
                    else if (map[row][next + 1] == map[row][col]) {
                        next++;
                        break;
                    } else
                        break;
                }

                if (next != col && !flag[row][next]) {
                    if (map[row][next] == 0) { // 단순 이동
                        map[row][next] = map[row][col];
                        map[row][col] = 0;
                    } else if (map[row][next] == map[row][col]) { // 합치기
                        map[row][next] *= 2;
                        map[row][col] = 0;
                        flag[row][next] = true;
                    }
                }
            }
        }

        return map;
    }

    private static int[][] copyMap(int[][] map) {
        int[][] copy = new int[N][N];
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[i], 0, copy[i], 0, N);
        }
        return copy;
    }

    private static void get_maxVal(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer = Math.max(answer, map[i][j]);
            }
        }
    }

    private static void print(int[][] map) {
        StringBuilder sb = new StringBuilder();
        sb.append('\n');

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(map[i][j]).append('\t');
            }
            sb.append('\n');
        }
        sb.append('\n');

        System.out.println(sb);
    }
}

🔸 코드 해석 🔸

• 게임판 정보를 2차원 int형 배열 map에 받아, dfs를 적용할 재귀 메서드 play_2048에 넣고 최대값을 구한다.
  • 깊이 정보가 5까지 오면 모든 인덱스를 확인해 최대값을 갱신한다.
  • 아직 깊이가 5까지 오지 않았으면, 상하좌우 순으로 이동한다.
• 상하좌우 이동은 간략히 다음과 같은 절차로 구현했다.
  • 이동하고자 하는 방향에서 가까운 인덱스부터 이동시켜 본다.
  • 갈 수 있는 인덱스 끝까지 이동한다.
  • 이동 X / 단순 이동 / 합치기 중에서 동작한다.

---

🔸 end 🔸

•  처음은 14%에서 틀렸는데, 오른쪽 이동의 조건이 틀렸다.
  • 두 번째는 2%에서 틀렸는데 다시보니 아래 이동의 조건도 같은 부분에서 틀렸다.
  • 상하좌우 비슷한 4가지 버전의 코드를 함께 변경하면서 두 종류의 변경이 미흡했다.
  • 한 번 틀렸으면 다른 종류도 확인했어야 했는데, 풀이 시간이 길어지다보니 집중력이 흐려진 것 같다.