[ BOJ / 백준 ] 2048 EASY (JAVA / 자바)

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

12100번: 2048 (Easy)

---

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

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

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

풀이

solution(int cnt) 함수가 메인 함수이다.
cnt가 5가 될 때까지 블록들을 이동시킨다

✅ 여기서 중요한 것은 최초 보드의 정보를 미리 저장해놓아야 한다!!

for(int i = 0; i < 4; i++) 를 돌면서, move(i) 함수로 각 방향으로 이동시킨다.

move(int dir)

• dir
  • 0 : 위쪽
    위 블록부터 이동
  • 1 : 왼쪽
    왼쪽 블록부터 이동
  • 2 : 오른쪽
    오른쪽 블록부터 이동
  • 3 : 아랫쪽
    밑 블록부터 이동

여기서 각 블록들은 moveBlock(int x, int y, int dir) 함수로 이동된다.
중요한 것은 x와 y 순서이다.

위쪽과 아랫쪽은 for문 순서가 행 → 열이고,
왼쪽과 오른쪽은 for문 순서가 열 → 행이다.

board[x][y]의 블록이 이동하는데,

1. 빈 공간(0)이라면 종료
2. 아니라면, dir방향(nx, ny)으로 이동
   1. (nx, ny)가 범위 밖이라면 종료
   2. (nx, ny)가 이미 앞에서 합쳐진 블럭이라면 종료
   3. 1,2번 둘다 만족하지 않고, (x,y)블록과 (nx,ny)블록이 같다면 합쳐주고 종료
   4. 1,2,3번 전부 아니고, 다른 블록이 존재한다면 종료
   5. 1,2,3,4번 전부 아니고, 빈 공간이라면 이동
3. 종료될 때까지 이동을 반복해준다.

이렇게 블록들을 5번 이동시켜주었다면 (cnt == 5)
블록의 최댓값을 저장 ‼️

생각보다 간단했는데,,,, 이동시키는 방법을 생각하기까지가 너무 어려웟당ㅠㅠ😭ㅠㅠ

---

코드

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

public class n_12100_2048_Easy {
    static int N, answer;
    static int[][] board;
    static boolean[][] isVisited;
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        answer = Integer.MIN_VALUE;
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];

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

        solution(0);

        System.out.println(answer);
    }

    private static void solution(int cnt) {
        if (cnt == 5) {
            findMax();
            return;
        }

        int[][] copyBoard = new int[N][N];
        for(int i = 0; i < N; i++) copyBoard[i] = board[i].clone();

        for (int i = 0; i < 4; i++) {
            move(i);
            solution(cnt + 1);

            for (int j = 0; j < N; j++) board[j] = copyBoard[j].clone();
        }


    }

    private static void findMax() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(answer < board[i][j]) answer = board[i][j];
            }
        }
    }

    private static void move(int dir) {
        isVisited = new boolean[N][N];
        switch (dir) {
            case 0:
                //up
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        moveBlock(i, j, dir);
                    }
                }
                break;
            case 1:
                //left
                for (int j = 0; j < N; j++) {
                    for (int i = 0; i < N; i++) {
                        moveBlock(i,j,dir);
                    }
                }
                break;
            case 2:
                //right
                for (int j = N - 1; j >= 0; j--) {
                    for (int i = 0; i < N; i++) {
                        moveBlock(i, j, dir);
                    }
                }
                break;
            case 3:
                //down
                for (int i = N - 1; i >= 0; i--) {
                    for (int j = 0; j < N; j++) {
                        moveBlock(i, j, dir);
                    }
                }
        }
    }

    private static void moveBlock(int x, int y, int dir) {
        if(board[x][y] == 0) return;

        while (true) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if(nx < 0 || ny < 0 || N <= nx || N <= ny) return;
            if(isVisited[nx][ny]) return;

            if(board[x][y] == board[nx][ny]){
                isVisited[nx][ny] = true;
                board[nx][ny] *= 2;
                board[x][y] = 0;
                return;
            }else if(board[nx][ny] != 0) return;

            board[nx][ny] = board[x][y];
            board[x][y] = 0;
            x = nx;
            y = ny;
        }
    }
}