[백준] 12100번 : 2048(Easy) - 자바(Java)

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

12100번: 2048 (Easy)

 

문제 해석

2048게임을 예전에 해본적이 있어서 이해가 어렵지 않았습니다.

만약 간단하게 한번 이 게임을 해본다면 더 이해하기 쉬울 것 같습니다.

https://play2048.co/

2048

 

문제의 규칙

• 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.
• 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐진다
• 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.
• 한번 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
• 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

문제 풀이 전 설계

상하좌우로 이동할 수 있는 경우 4가지, 최대 이동횟수 5번(최대 이동횟수가 최댓값을 가질 수 밖에 없다고 판단)

따라서 무조건 5번이동하고 결과찾기

 

경우의 수 : 4 * 4 * 4 * 4 * 4 = 4^5 = 2^10 = 1,024

보드의 크기 N은 20이하의 수이므로 N^2 = 400

문제에서 제시하는 수들이 작기 때문에 완전탐색쪽으로 풀이해보고자 합니다.

 

 

코드

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

/*

문제 풀이 방식 예제
기존 board
2 2 0 2
2 0 0 2
2 2 0 0
2 0 2 2

moveUp()이후
2 2 2 2
2 2 0 2
2 0 0 2
2 0 0 0

mergeUp()이후
4 4 2 4
0 0 0 0
4 0 0 2
0 0 0 0

moveUp()이후
4 4 2 4
4 0 0 2
0 0 0 0
0 0 0 0

한사이클 완료


 */

enum Direction {
    UP, DOWN, LEFT, RIGHT, NONE
}

public class Main_12100_2048 {

    static int[][] board;
    static final int PLAY_TIME = 5;
    static int result = Integer.MIN_VALUE;
    static int N;

    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];

        StringTokenizer st = null;
        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x = 0; x < N; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        playGame(Direction.NONE, 0, board);
        System.out.println(result);

    }

    private static void playGame(Direction direction, int cnt, int[][] board) {
        if (cnt == 6) {
            result = Math.max(findMaxValue(board), result);
            return;
        }
        int[][] copiedBoard = null;

        if (direction == Direction.UP) {
            copiedBoard = Arrays.stream(board).map(int[]::clone).toArray(int[][]::new);
            moveUp(copiedBoard);
            mergeUp(copiedBoard);
            moveUp(copiedBoard);
        }

        if (direction == Direction.DOWN) {
            copiedBoard = Arrays.stream(board).map(int[]::clone).toArray(int[][]::new);
            moveDown(copiedBoard);
            mergeDown(copiedBoard);
            moveDown(copiedBoard);
        }

        if (direction == Direction.LEFT) {
            copiedBoard = Arrays.stream(board).map(int[]::clone).toArray(int[][]::new);
            moveLeft(copiedBoard);
            mergeLeft(copiedBoard);
            moveLeft(copiedBoard);
        }

        if (direction == Direction.RIGHT) {
            copiedBoard = Arrays.stream(board).map(int[]::clone).toArray(int[][]::new);
            moveRight(copiedBoard);
            mergeRight(copiedBoard);
            moveRight(copiedBoard);
        }

        if (copiedBoard == null) {
            copiedBoard = board;
        }

        playGame(Direction.UP, cnt + 1, copiedBoard);
        playGame(Direction.DOWN, cnt + 1, copiedBoard);
        playGame(Direction.LEFT, cnt + 1, copiedBoard);
        playGame(Direction.RIGHT, cnt + 1, copiedBoard);

    }


    private static void moveUp(int[][] copiedBoard) {
        //위쪽으로 빈칸 없게 모두 이동
        for (int y = 1; y < N; y++) {
            for (int x = 0; x < N; x++) {
                int tempY = y;
                while (copiedBoard[tempY - 1][x] == 0) {
                    copiedBoard[tempY - 1][x] = copiedBoard[tempY][x];
                    copiedBoard[tempY][x] = 0;

                    if (tempY - 2 == -1) {
                        break;
                    }
                    tempY--;
                }
            }
        }
    }

    private static void moveRight(int[][] copiedBoard) {
        //오른쪽으로 빈칸 없게 모두 이동
        for (int x = N - 2; x >= 0; x--) {
            for (int y = 0; y < N; y++) {
                int tempX = x;
                while (copiedBoard[y][tempX + 1] == 0) {
                    copiedBoard[y][tempX + 1] = copiedBoard[y][tempX];
                    copiedBoard[y][tempX] = 0;

                    if (tempX + 2 == N) {
                        break;
                    }
                    tempX++;
                }
            }
        }
    }

    private static void moveLeft(int[][] copiedBoard) {
        //왼쪽으로 빈칸 없게 모두 이동
        for (int x = 1; x < N; x++) {
            for (int y = 0; y < N; y++) {
                int tempX = x;
                while (copiedBoard[y][tempX - 1] == 0) {
                    copiedBoard[y][tempX - 1] = copiedBoard[y][tempX];
                    copiedBoard[y][tempX] = 0;

                    if (tempX - 2 == -1) {
                        break;
                    }
                    tempX--;
                }
            }
        }
    }

    private static void moveDown(int[][] copiedBoard) {
        //아래쪽으로 빈칸 없게 모두 이동
        for (int y = N - 2; y >= 0; y--) {
            for (int x = 0; x < N; x++) {
                int tempY = y;
                while (copiedBoard[tempY + 1][x] == 0) {
                    copiedBoard[tempY + 1][x] = copiedBoard[tempY][x];
                    copiedBoard[tempY][x] = 0;

                    if (tempY + 2 == N) {
                        break;
                    }
                    tempY++;
                }
            }
        }
    }

    private static void mergeUp(int[][] copiedBoard) {
        //이미 위쪽으로 모두 몰려있는 상황
        for(int y=1; y<N; y++){
            for(int x=0; x<N; x++){
                if(copiedBoard[y][x] == copiedBoard[y-1][x]){
                    copiedBoard[y-1][x] *= 2;
                    copiedBoard[y][x] = 0;
                }
            }
        }
    }

    private static void mergeDown(int[][] copiedBoard) {
        //이미 아래쪽으로 모두 몰려있는 상황
        for(int y=N-2; y>=0; y--){
            for(int x=0; x<N; x++){
                if(copiedBoard[y][x] == copiedBoard[y+1][x]){
                    copiedBoard[y+1][x] *= 2;
                    copiedBoard[y][x] = 0;
                }
            }
        }
    }

    private static void mergeLeft(int[][] copiedBoard) {
        //이미 왼쪽으로 모두 몰려있는 상황
        for(int x=1; x<N; x++){
            for(int y=0; y<N; y++){
                if(copiedBoard[y][x] == copiedBoard[y][x-1]){
                    copiedBoard[y][x-1] *= 2;
                    copiedBoard[y][x] = 0;
                }
            }
        }
    }

    private static void mergeRight(int[][] copiedBoard) {
        //이미 오른쪽으로 모두 몰려있는 상황
        //이미 왼쪽으로 모두 몰려있는 상황
        for(int x=N-2; x>=0; x--){
            for(int y=0; y<N; y++){
                if(copiedBoard[y][x] == copiedBoard[y][x+1]){
                    copiedBoard[y][x+1] *= 2;
                    copiedBoard[y][x] = 0;
                }
            }
        }
    }


    static int findMaxValue(int[][] board) {
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < board.length; i++) {
            maxValue = Math.max(maxValue, Arrays.stream(board[i]).max().getAsInt());
        }

        return maxValue;
    }

}