[BaekJoon] 12100 2048 (Easy) Java

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int N, max;
    static int[][] board;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        board = new int[N][N];

        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++)
                board[row][col] = scanner.nextInt();
        }
    }

    static void solution() {
        max = 2;
        move(0, board);

        System.out.println(max);
    }

    static void move(int moveNum, int[][] board) {
        if(moveNum == 5) {
            findMax(board);
            return;
        }

        move(moveNum + 1, moveUp(board));
        move(moveNum + 1, moveDown(board));
        move(moveNum + 1, moveLeft(board));
        move(moveNum + 1, moveRight(board));
    }

    static void findMax(int[][] board) {
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++)
                max = Math.max(max, board[row][col]);
        }
    }

    static int[][] moveUp(int[][] board) {
        int[][] boardCopy = new int[N][N];
        Queue<Integer> queue = new LinkedList<>();

        for(int col = 0; col < N; col++) {
            for(int row = 0; row < N; row++)
                if(board[row][col] != 0) queue.offer(board[row][col]);

            int index = 0;
            while(!queue.isEmpty()) {
                int cur = queue.poll();

                if(boardCopy[index][col] == 0) boardCopy[index][col] = cur;
                else if(boardCopy[index][col] == cur) boardCopy[index++][col] = cur * 2;
                else boardCopy[++index][col] = cur;
            }
        }

        return boardCopy;
    }

    static int[][] moveDown(int[][] board) {
        int[][] boardCopy = new int[N][N];
        Queue<Integer> queue = new LinkedList<>();

        for(int col = 0; col < N; col++) {
            for(int row = N - 1; row >= 0; row--)
                if(board[row][col] != 0) queue.offer(board[row][col]);

            int index = N - 1;
            while(!queue.isEmpty()) {
                int cur = queue.poll();

                if(boardCopy[index][col] == 0) boardCopy[index][col] = cur;
                else if(boardCopy[index][col] == cur) boardCopy[index--][col] = cur * 2;
                else boardCopy[--index][col] = cur;
            }
        }

        return boardCopy;
    }

    static int[][] moveLeft(int[][] board) {
        int[][] boardCopy = new int[N][N];
        Queue<Integer> queue = new LinkedList<>();

        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++)
                if(board[row][col] != 0) queue.offer(board[row][col]);

            int index = 0;
            while(!queue.isEmpty()) {
                int cur = queue.poll();

                if(boardCopy[row][index] == 0) boardCopy[row][index] = cur;
                else if(boardCopy[row][index] == cur) boardCopy[row][index++] = cur * 2;
                else boardCopy[row][++index] = cur;
            }
        }

        return boardCopy;
    }

    static int[][] moveRight(int[][] board) {
        int[][] boardCopy = new int[N][N];
        Queue<Integer> queue = new LinkedList<>();

        for(int row = 0; row < N; row++) {
            for(int col = N - 1; col >= 0; col--)
                if(board[row][col] != 0) queue.offer(board[row][col]);

            int index = N - 1;
            while(!queue.isEmpty()) {
                int cur = queue.poll();

                if(boardCopy[row][index] == 0) boardCopy[row][index] = cur;
                else if(boardCopy[row][index] == cur) boardCopy[row][index--] = cur * 2;
                else boardCopy[row][--index] = cur;
            }
        }

        return boardCopy;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• board라는 2차원 배열에 주어진 게임판의 초기 정보를 저장하고 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 나타내는 변수 max를 생성하고 값을 2로 초기화합니다.
  • 문제에서 최소 1개의 블록이 존재한다고 하였으므로 2로 초기화합니다.
• 재귀를 통해 모든 이동시킬 수 있는 경우에 대해 이동시켜보면서 최대 블록을 찾습니다.
  • 이동시키는 방법은 위, 아래, 왼쪽, 오른쪽이 있는데 로직은 비슷하기 때문에 위쪽으로 이동하는 로직을 통해 살펴보겠습니다.
  • 우선 이동시킨 후의 게임판을 나타내는 2차원 배열 boardCopy를 생성하고 각 열에서 비어있지 않은 블록들을 위에서부터 차례대로 넣은 Queue인 queue를 생성합니다.
  • 각 열을 순회하면서 아래 작업을 진행합니다.
    • 위에서부터 아래로 순회하면서 블록이 있는 곳에서의 수를 queue에 담습니다.
    • 이동시킨 후에 블록을 채울 위치를 나타내는 index라는 변수를 생성하고 0으로 값을 초기화합니다.
    • queue가 빌 때까지 수를 하나씩 꺼내서 이동시킨 후의 게임판을 채웁니다.
    • 만약 boardCopy에서 현재 index에 해당하는 위치가 0이라면, 비어있으므로 현재 꺼낸 블록을 해당 위치에 놓습니다.
    • 만약 boardCopy에서 현재 index에 해당하는 위치가 꺼낸 수와 같다면, 현재 꺼낸 블록과 합쳐질 수 있다는 뜻이므로 현재 값의 2배로 값을 설정하고 한 번 합쳐졌기 때문에 더이상 이 위치의 블록은 합쳐질 수 없으니 index를 1 증가시킵니다.
    • 만약 위 두 경우 모두 아니라면, index에 해당하는 위치가 0이 아니면서 현재 블록과 다른 값이라는 뜻이므로 index 위치에 있는 블록과 합쳐질 수 없으니 다음 칸에 현재 블록을 담기 위해 index를 1 증가시키고 그 위치에 블록을 담습니다.
  • 이동시킨 후에 가장 큰 블록의 수를 찾고 최댓값을 갱신시킵니다.