[BOJ] 백준 12100 2048(Easy)

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 
3
2 2 2
4 4 4
8 8 8

 Output 

16

2048 게임을 구현하는 문제입니다.

- 한 번의 이동은 보드 위에 전체 블록을 상하좌우 네 방향 중 하나로 이동

- 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.

- 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.

　

4 × 4 크기의 보드에서 게임을 진행하면 다음과 같습니다.

(실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.)

▷ 위쪽, 왼쪽으로 이동한 결과

▷ 오른쪽, 위쪽, 오른쪽으로 이동

▷ 왼쪽 이동

▷ 위쪽 이동

▷ 위쪽 이동 (한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없음)

▷ 위쪽 이동 (똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.)

N × N 크기의 보드판에 숫자가 주어질 때, (1 ≤ N ≤ 20)

최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하시오.

(0: 빈칸 / 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이며, 블록은 적어도 하나 주어짐)

 

구현 사항

상, 하, 좌, 우 이렇게 총 4가지 방향을 5번 움직이므로

4 × 4 × 4 × 4 × 4 = 1024 경우의 수가 나옵니다.

각 Case 중 가장 큰 블록의 값을 구하면됩니다. (중복 가능한 순열)

 

주어지는 블럭의 위치, 개수, 숫자에 따라 결과가 달라지며, N이 크지 않은 수 이기 때문에

완전탐색을 통하여 해결할 수 있습니다.

이 문제는 2048 게임에서 블럭이 합쳐지는(Merge) 것을 어떻게 구현할지 입니다.

 

▶ Stack을 이용한 완전탐색. (LIFO 구조)

① 보드상에서 한 줄 단위로 처리합니다.

    board[][] = [4 4 8 8]

    stack = [ ]

② 스택이 비워져 있는 경우 push

    ※ board[][]에서 실제 원소가 없어진 것으 아니지만 설명을 위해 삭제 표시

    board[][] = [4 8 8]

    stack = [4]

③ Stack에 원소가 있는 경우 pop하여 같은 값인지 확인 & 이미 합쳐진 숫자 확인

    (같은 값이면서 합쳐지지 않은 숫자인 경우) pop했던 원소와 합친 결과를 push

    그렇지 않은 경우 stack에 pop한 원소와 board[][]의 원소를 차례대로 push

    board[][] = [8 8]

    stack = [8]

④ 위 ③의 작업을 board[][] 원소를 모두 처리할 때까지 반복.

    이미 합쳐진 원소가 stack에 있으므로 원소 『8』 push

    board[][] = [8]

    stack = [8 8]

⑤ 값은 값이면서 합쳐지지 않은 숫자이므로 pop한 후, 합친 결과를 Push

    board[][] = []

    stack = [8 16]

⑥ 스택에 있는 원소를 board[][]배열에 처음부터 배치합니다.

    board[][] = [8 16 0 0]

    stack = []

※ 상하좌우는 방향의 차이이므로 동일한 방식으로 구현.

---

import java.io.*;
import java.util.*;
 
public class Main {
    static final int EMPTY = 0, UP = 1, DOWN = 2, LEFT = 3, RIGHT = 4;
    static int[] moveArr, direction = { 0, UP, DOWN, LEFT, RIGHT };
    static int[][] orginalBoard, board;
    static int N, answer = Integer.MIN_VALUE;
    static Stack<Block> stack;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
        orginalBoard = new int[N + 1][N + 1];
        moveArr = new int[5 + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                orginalBoard[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 중복 가능한 순열을 통해 5번의 이동방향 순서를 구합니다.
        permutation(1);
 
        // 정답출력
        System.out.println(answer);
    }
 
    private static void permutation(int idx) {
        if (idx > 5) {
            // 이차원 배열 깊은 복사
            board = deepCopy(orginalBoard);
            // 2048 게임 시작
            gameStart();
            return;
        }
 
        for (int i = 1; i <= 4; i++) {
            // 뽑은 원소를 결과값에 대입시킨다.
            moveArr[idx] = direction[i];
            // 다음 자리의 문자열을 재귀로 탐색해서 채워간다.
            permutation(idx + 1);
        }
 
    }
 
    private static void gameStart() {
        for(int i=1; i<=5; i++) {
            switch (moveArr[i]) {
            case UP:
                upMove();
                break;
            case DOWN:
                downMove();
                break;
            case LEFT:
                leftMove();
                break;
            case RIGHT:
                rightMove();
                break;
            }
        }
         
        // 블럭의 최대값 탐색
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                answer = Math.max(answer, board[i][j]);
            }
        }
         
    }
 
    private static void upMove() {
        for(int j=1; j<=N; j++) {
            stack = new Stack<>();
            for(int i=1; i<=N; i++) {
                if(board[i][j] == EMPTY) continue;
                 
                if(stack.isEmpty()) {
                    stack.add(new Block(board[i][j]));
                    continue;
                }
                // 스택이 비워져 있지 않은 경우
                Block prev = stack.pop();
                if((prev.value == board[i][j]) && (!prev.isMerge)) {
                    Block mergedBlock = new Block(prev.value + board[i][j]);
                    mergedBlock.isMerge = true;
                    stack.add(mergedBlock);
                }else {
                    stack.add(prev);
                    stack.add(new Block(board[i][j]));
                }
            }
             
            for(int i=1; i<=N; i++) {
                if(!stack.isEmpty()) {
                    board[i][j] = stack.remove(0).value;
                }else {
                    board[i][j] = 0;
                }
            }
        }
    }
 
    private static void downMove() {
        for(int j=1; j<=N; j++) {
            stack = new Stack<>();
            for(int i=N; i>=1; i--) {
                if(board[i][j] == EMPTY) continue;
                 
                if(stack.isEmpty()) {
                    stack.add(new Block(board[i][j]));
                    continue;
                }
                // 스택이 비워져 있지 않은 경우
                Block prev = stack.pop();
                if((prev.value == board[i][j]) && (!prev.isMerge)) {
                    Block mergedBlock = new Block(prev.value + board[i][j]);
                    mergedBlock.isMerge = true;
                    stack.add(mergedBlock);
                }else {
                    stack.add(prev);
                    stack.add(new Block(board[i][j]));
                }
            }
             
            for(int i=N; i>=1; i--) {
                if(!stack.isEmpty()) {
                    board[i][j] = stack.remove(0).value;
                }else {
                    board[i][j] = 0;
                }
            }
        }
    }
 
    private static void leftMove() {
        for(int i=1; i<=N; i++) {
            stack = new Stack<>();
            for(int j=1; j <= N; j++) {
                if(board[i][j] == EMPTY) continue;
                 
                if(stack.isEmpty()) {
                    stack.add(new Block(board[i][j]));
                    continue;
                }
                // 스택이 비워져 있지 않은 경우
                Block prev = stack.pop();
                if((prev.value == board[i][j]) && (!prev.isMerge)) {
                    Block mergedBlock = new Block(prev.value + board[i][j]);
                    mergedBlock.isMerge = true;
                    stack.add(mergedBlock);
                }else {
                    stack.add(prev);
                    stack.add(new Block(board[i][j]));
                }
            }
             
            for(int j = 1; j <= N; j++) {
                if(!stack.isEmpty()) {
                    board[i][j] = stack.remove(0).value;
                }else {
                    board[i][j] = 0;
                }
            }
        }
    }
 
    private static void rightMove() {
        for(int i=1; i<=N; i++) {
            stack = new Stack<>();
            for(int j=N; j >= 1; j--) {
                if(board[i][j] == EMPTY) continue;
                 
                if(stack.isEmpty()) {
                    stack.add(new Block(board[i][j]));
                    continue;
                }
                // 스택이 비워져 있지 않은 경우
                Block prev = stack.pop();
                if((prev.value == board[i][j]) && (!prev.isMerge)) {
                    Block mergedBlock = new Block(prev.value + board[i][j]);
                    mergedBlock.isMerge = true;
                    stack.add(mergedBlock);
                }else {
                    stack.add(prev);
                    stack.add(new Block(board[i][j]));
                }
            }
             
            for(int j=N; j >= 1; j--) {
                if(!stack.isEmpty()) {
                    board[i][j] = stack.remove(0).value;
                }else {
                    board[i][j] = 0;
                }
            }
        }
    }
 
    private static int[][] deepCopy(int[][] array) {
        if (array == null) return null;
         
        int[][] copyArray = new int[array.length][array[0].length];
        for (int i = 0; i < array.length; i++) {
            System.arraycopy(array[i], 0, copyArray[i], 0, array[0].length);
        }
        return copyArray;
    }
}
 
class Block {
    int value;
    boolean isMerge;
 
    public Block(int value) {
        this.value = value;
        isMerge = false;
    }   
}