자바(Java) 백준 2048(easy) 풀이

문제

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

[12100번: 2048 (Easy)

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2

www.acmicpc.net](https://www.acmicpc.net/problem/12100)

풀이

이 문제는 dfs를 사용하여 접근하였습니다.

• 경우의 수는 상, 하, 좌, 우 4가지 경우의 수가 있습니다.
• 따라서 for 문으로 4가지 방향에 대해서 블록을 이동시켜줍니다.
• 기존 board 배열에서 copy 라는 새로운 배열을 만들어줘서 한줄씩 이동시켜줍니다.
• 값이 0이 아닌 경우에 값을 옮깁니다.
• 이 때 이전에 옮긴 값과 현재 값을 합칠 지 확인해야합니다.
  • 만약 이전에 옮긴 값이 없다면 합치지 않고 그대로 옮겨줍니다.
  • 이전에 옮긴 값과 현재 값이 같다면 두 값을 합쳐주고 visited 라는 불린값을 true로 체크해줍니다.
  • 값이 다르다면 그대로 옮겨주고 visited 값을 false로 합니다.
• 이렇게 5번 반복한다면 블록안에서 최대값이 있는지 확인하고 있다면 max 값을 갱신합니다.

코드

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

public class Main {

    static int n;
    static int[][] board;
    static int max = 0;

    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 i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        game(0);
        System.out.println(max);
    }

    public static void game(int cnt) {
        // 5번 움직인 경우 배열에서 가장 큰값이 있다면 max를 갱신합니다.
        if (cnt == 5) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    max = Math.max(max, board[i][j]);
                }
            }
            return;
        }

        for (int d = 0; d < 4; d++) {
            int[][] copy = new int[n][n];
            switch (d) {
                // 위로 움직임
                case 0:
                    for (int i = 0; i < n; i++) {
                        int idx = 0;
                        boolean visited = false;
                        for (int j = 0; j < n; j++) {
                            // 현재 위치의 값이 0이 아닌경우 위치를 옮겨야함
                            if (board[i][j] != 0) {
                                if (idx == 0) {
                                    // 처음으로 움직이는 값인 경우
                                    copy[i][idx] = board[i][j];
                                    idx++;
                                } else {
                                    if (!visited && copy[i][idx - 1] == board[i][j]) {
                                        // 그 전 값이 합쳐지지 않았고 두 값이 같은 경우 합쳐야합니다.
                                        copy[i][idx - 1] *= 2;
                                        visited = true;
                                    } else {
                                        copy[i][idx] = board[i][j];
                                        visited = false;
                                        idx++;
                                    }
                                }
                            }
                        }
                    }
                    break;
                // 아래로 움직임
                case 1:
                    for (int i = 0; i < n; i++) {
                        int idx = n - 1;
                        boolean visited = false;
                        for (int j = n - 1; j >= 0; j--) {
                            // 현재 위치의 값이 0이 아닌경우 위치를 옮겨야함
                            if (board[i][j] != 0) {
                                if (idx == n - 1) {
                                    // 처음으로 움직이는 값인 경우
                                    copy[i][idx] = board[i][j];
                                    idx--;
                                } else {
                                    if (!visited && copy[i][idx + 1] == board[i][j]) {
                                        // 그 전 값이 합쳐지지 않았고 두 값이 같은 경우 합쳐야합니다.
                                        copy[i][idx + 1] *= 2;
                                        visited = true;
                                    } else {
                                        copy[i][idx] = board[i][j];
                                        visited = false;
                                        idx--;
                                    }
                                }
                            }
                        }
                    }
                    break;
                // 왼쪽으로 움직임
                case 2:
                    for (int i = 0; i < n; i++) {
                        int idx = 0;
                        boolean visited = false;
                        for (int j = 0; j < n; j++) {
                            // 현재 위치의 값이 0이 아닌경우 위치를 옮겨야함
                            if (board[j][i] != 0) {
                                if (idx == 0) {
                                    // 처음으로 움직이는 값인 경우
                                    copy[idx][i] = board[j][i];
                                    idx++;
                                } else {
                                    if (!visited && copy[idx - 1][i] == board[j][i]) {
                                        // 그 전 값이 합쳐지지 않았고 두 값이 같은 경우 합쳐야합니다.
                                        copy[idx - 1][i] *= 2;
                                        visited = true;
                                    } else {
                                        copy[idx][i] = board[j][i];
                                        visited = false;
                                        idx++;
                                    }
                                }
                            }
                        }
                    }
                    break;
                // 오른쪽으로 움직임
                case 3:
                    for (int i = 0; i < n; i++) {
                        int idx = n - 1;
                        boolean visited = false;
                        for (int j = n - 1; j >= 0; j--) {
                            // 현재 위치의 값이 0이 아닌경우 위치를 옮겨야함
                            if (board[j][i] != 0) {
                                if (idx == n - 1) {
                                    // 처음으로 움직이는 값인 경우
                                    copy[idx][i] = board[j][i];
                                    idx--;
                                } else {
                                    if (!visited && copy[idx + 1][i] == board[j][i]) {
                                        // 그 전 값이 합쳐지지 않았고 두 값이 같은 경우 합쳐야합니다.
                                        copy[idx + 1][i] *= 2;
                                        visited = true;
                                    } else {
                                        copy[idx][i] = board[j][i];
                                        visited = false;
                                        idx--;
                                    }
                                }
                            }
                        }
                    }
            }

            int[][] tmp = new int[n][n];
            for (int i = 0; i < n; i++) {
                tmp[i] = board[i].clone();
            }
            board = copy;
            game(cnt + 1);
            board = tmp;
        }
    }
}