[백준 12100번] 2048(Easy)

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

 

package implement;

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

public class Impl12100 {
    static int answer = 0;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        int[][] 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, board);
        System.out.println(answer);
    }

    private static void solution(int depth, int[][] board) {
        if (depth == 5) {
            answer = Math.max(answer, getMax(board));
            return;
        }


        for (int dir = 0; dir < 4; dir++) {
            int[][] move = move(dir, board);
            solution(depth+1, move);
        }
    }

    private static int getMax(int[][] board) {
        int max = 0;
        for (int[] row : board) {
            for (int val : row) {
                max = Math.max(max, val);
            }
        }
        return max;
    }

    private static int[][] move(int dir, int[][] board) {
        int [][] newBoard = new int[N][N];

        for(int i=0; i<N; i++){
            int []temp =new int[N];
            int idx = 0;
            boolean merge=false;
            for(int j=0; j<N; j++){
                int x,y;
                if(dir ==0){
                    x=j;
                    y=i;
                }else if(dir ==1){
                    x=i;
                    y=j;
                }else if(dir ==2){
                    x= N-1-j;
                    y= i;
                }else{
                    x=i;
                    y= N-1-j;
                }
                int value = board[x][y];
                if(value ==0){
                    continue;
                }

                if(idx !=0 && temp[idx-1] == value &&!merge){
                    temp[idx-1] *=2;
                    merge=true;
                }else{
                    temp[idx] = value;
                    idx++;
                    merge=false;
                }
            }

            for(int j=0; j<N; j++){
                if(dir==0){
                    newBoard[j][i] = temp[j];
                }else if(dir ==1){
                    newBoard[i][j] = temp[j];
                }else if(dir ==2){
                    newBoard[N-1-j][i] =temp[j];
                }else{
                    newBoard[i][N-1-j] =temp[j];
                }
            }

        }

        return newBoard;

    }
}

 

 

이 문제는 정말 감탄이 나오는 문제다.

핵심은 얕은 복사를 이용해 이전 배열을 참조한 채 재귀를 호출하면 원본 배열이 손상되지 않는다는 점이다. 또한 temp와 idx를 활용하면 블록을 한 번에 밀고 병합하는 과정을 효율적으로 처리할 수 있다.