[BaekJoon] 백준 - 2048 (Easy)

예전에 유행했던 2048 게임을 코드로 구현하는 문제. 

 

그림이 첨부되어 있어 자세한 문제는 백준에서 확인 할 수 있다. 

 

 

 

5번의 움직임 내에 가장 큰 값을 도출해야하는 문제.

 

모든 경우의 수를 확인해야하기 때문에 dfs로 풀었다. 

 

import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int MAX;
    static int N;
    static int[][] MATRIX;
    
    static class Number {
        int number;
        boolean isAdd;
        
        public Number(int number, boolean isAdd) {
            this.number = number;
            this.isAdd = isAdd;
        }
        
        public void setNumber(int number) {
            this.number = number;
        }
        
        public void setAdd(boolean isAdd) {
            this.isAdd = isAdd;
        }
        
        public int getNumber() {
            return this.number;
        }
        
        public boolean isAdd() {
            return this.isAdd;
        }
    }
    
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        scanner.nextLine();
    
        MAX = 2;
        
        MATRIX = new int[N][N];
        
        for(int i = 0; i<N; i++) {
            String str = scanner.nextLine();
            String[] tmp = str.split(" ");
            
            for(int j = 0; j<N; j++) {
                MATRIX[i][j] = Integer.parseInt(tmp[j]);
            }
        }
        
        dfs(1);
        
        System.out.println(MAX);
      
    }
    
    public static void dfs(int count) {
        if (count > 5) {
            for(int i = 0; i<N; i++) {
                for(int j = 0; j<N; j++) {
                    MAX = Math.max(MAX, MATRIX[i][j]);
                }
            }
            return;
        }
        
        int[][] tmp = deepCopy(MATRIX);
        
        for(int i = 0; i<4; i++) {
            move(i);
            dfs(count+1);
            MATRIX = deepCopy(tmp);
        }
        
        
    }
    
    public static void move(int dir) {
        Stack<Number> stack = new Stack<>();
    
        // up
        if (dir == 0) {
            for(int i = 0; i< N; i++) {
                for(int j = 0; j<N; j++) {
                    int target = MATRIX[j][i];
                    
                    if (target == 0) continue;
                    MATRIX[j][i] = 0;
                    
                    if (!stack.isEmpty()) {
                        Number n = stack.pop();
                        
                        if (n.getNumber() == target && !n.isAdd()) {
                            n.setNumber(n.getNumber() * 2);
                            n.setAdd(true);
                            stack.push(n);
                            continue;
                        }
                        stack.push(n);
                    }
                    
                    stack.push(new Number(target, false));
                }
                
                for(int j = stack.size() - 1; j >= 0; j--) {
                    MATRIX[j][i] = stack.pop().getNumber();
                }
            }
        }
        
        // down
        else if (dir == 1) {
            for(int i = 0; i<N; i++) {
                for(int j = N-1; j>=0; j--) {
                    int target = MATRIX[j][i];
    
                    if (target == 0) continue;
                    MATRIX[j][i] = 0;
                    
                    if (!stack.isEmpty()) {
                        Number n = stack.pop();
                        
                        if (n.getNumber() == target && !n.isAdd()) {
                            n.setNumber(n.getNumber() * 2);
                            n.setAdd(true);
                            stack.push(n);
                            continue;
                        }
                        stack.push(n);
                    }
                    
                    stack.push(new Number(target, false));
                }
                
                for(int j = N - stack.size(); j<N; j++) {
                     MATRIX[j][i] = stack.pop().getNumber();
                }
            }
        }
        
        // left
        else if (dir == 2) {
            for(int i = 0; i<N; i++) {
                for(int j = 0; j<N; j++) {
                    int target = MATRIX[i][j];
    
                    if (target == 0) continue;
                    MATRIX[i][j] = 0;
                    
                    if (!stack.isEmpty()) {
                        Number n = stack.pop();
                        
                        if (n.getNumber() == target && !n.isAdd()) {
                            n.setNumber(n.getNumber() * 2);
                            n.setAdd(true);
                            stack.push(n);
                            continue;
                        }
                        stack.push(n);
                    }
                    stack.push(new Number(target, false));
                }
                
                for(int j = stack.size() - 1; j >= 0; j--) {
                   MATRIX[i][j] = stack.pop().getNumber();
                }
            }
        }
        
        // right
        else if (dir == 3) {
            for(int i = 0; i<N; i++) {
                for(int j = N-1; j>=0; j--) {
                    int target = MATRIX[i][j];
    
                    if (target == 0) continue;
                    MATRIX[i][j] = 0;
                    
                    if (!stack.isEmpty()) {
                        Number n = stack.pop();
                        
                        if (n.getNumber() == target && ! n.isAdd()) {
                            n.setNumber(n.getNumber() * 2);
                            n.setAdd(true);
                            stack.push(n);
                            continue;
                        }
                        stack.push(n);
                    }
                    stack.push(new Number(target, false));
                }
                
                for(int j = N - stack.size(); j < N; j++) {
                   MATRIX[i][j] = stack.pop().getNumber();
                }
            }
        }
    }
    
    public static int[][] deepCopy(int[][] target) {
        int[][] newArray = new int[N][N];
        
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<N; j++) {
                newArray[i][j] = target[i][j];
            }
        }
        
        return newArray;
    }
}

 

 

동 서 남 북 4가지 방향을 모두 탐색해야하고

move 를 통해 실제 방향으로 숫자들을 움직였다. 

 

움직일 때는 Stack 에 방향에 맞는 값을 넣고 stack 에 숫자가 들어있다면 현재 체크해야하는 숫자와 비교하여 같으면 병합하고

아니면 push 한다.

 

단 한번 병합된 숫자는 다시 합칠 수 없기 때문에 flag를 따로 설정해주어야 한다. 

 

숫자가 다르다면 합치지 않고 그대로 stack에 넣어준다. 

숫자가 0일 때는 넣지 않는다. 

 

 

move가 끝난 이후에는 스택의 크기에 맞춰서 배열에 재배치 해주어야한다.