[백준] Q12100 2048(Easy) JAVA

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

12100번: 2048 (Easy)

1. 문제의 유형 및 이해

구현, 완전탐색, 시뮬레이션

유행했던 2048 게임을 구현하는 문제이다.

문제에서 주어진 조건들을 생각하며 순차적으로 구현한다.

최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하자.

 

한 번 이동시 4회의 이동을 가진다. 최대 5번이기 때문에 $4^5 = 1024$ 안에 해결이 가능하다.

 

2. 문제 접근 방법

문제가 까다로운 이유와 몇가지 생각할 것이 있었다.

1. 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

 즉, 2 2 2이고 >>로 밀면 0 2 4가 되어야 하고 <<로 밀면 4 2 0 이 되어야 한다는 점이다.

 질문 게시판을 보았을 때 이러한 부분을 놓치는 사람이 꽤 있었던 것 같다.

 이 부분에 대해 x,y좌표에 대해 헷갈린다면 꽤나 시간이 많이 걸릴 것 같다.

처음 구현 시에는 단순 배열로 구현하여 진행했고, review를 하면서 stack을 통해 진행했는데 stack을 사용한다고 메모리만 잡아먹었지 결국 같은 로직이라 배열로 단순 구현하는 것이 더 좋을 것이다. 실제로 시간도 더 빠르게 나왔다.

 움직여서 들어갈 위치를 잘 추적하며 구현하면 된다.

2. 백트래킹?

 백트래킹 방법을 시도하려고 햇었다. 2048 게임 특성상 갔던 방향을 또 갔을 때도 변화가 있을 수 있고

왔던 방향 반대로 간다고 그대로 있지도 않기 때문에 매번 4방향에 대해 탐색해주어야 하는 것이 맞다.

백트래킹을 하기 위해서 몇 가지 생각을 했었는데,

 1. MAX값이 바뀌지 않는다? 이건 아니다.

 2. moving한 block이 없다. 

    이 부분은 사실 그 전 방향과 같은 방향으로 움직였을 때  또는 더이상 움직일 블럭이 없을 때 가능한데, 

    더 이상 움직일 블럭이 없다는 가정은 빈공간이 하나라도 있다면 어디든 못해도 3방향은 움직일 수 있고,

    하나의 방향만 처리해주기 위해 백트래킹하기에는 counting하는 연산이 아까웠다.

수가 1024개로 그리 크지 않다고 생각하여 그대로 진행했다.

3. 배열의 복사

 특히 얕은 복사와 깊은 복사에 대해 헷갈려 여러번 moving을 하는 동안 원 배열이 아닌 바뀐 배열로 다시 작업을 하는 경우도 있을 수 있기 때문에 잘 복사를 해 주어야 한다. 

  배열의 복사하는 로직이 별로 마음에 들지 않아서 moving하는 함수에서 아예 int[][] 배열을 반환하여 사용하였다.

 

정리하자면, 완전탐색 4방향에 대해 5번 돌리면 된다. 그리고 각 방향마다 움직이는 로직만 잘 구현한다면 쉽게 통과할 수 있을 것이다.

구현에서는 Review할 때 사용한 stack으로 적어두지만, 다시 푼다면 변수로 푸는 것이 더 빠르고 좋다.

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

/**
 * @문제번호 : Q12100
 * @문제이름 : 2048
 * @난이도 : GoldII
 * @date : 2022-02-18 오후 4:29
 * @author : pcrmcw0486
 * @문제이해
 * 2048게임 만들기
 * @알고리즘
 * 그냥 빡 구현인거 같은데
 * 백트래킹. 완탐. < > 가 같지 않기 때문에.
 * pruning 함수는 움직임이 없을때.
 * 최대 5번 이동해서 만들 수 있는 가장 큰 블록
 * @접근방법

*/

public class Main {
    static int N;
    static int max;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }
        solve(map, 0);
        System.out.println(max);
    }

    public static void solve(int[][] map, int depth) {
        if (depth == 5) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    max = Math.max(max, map[i][j]);
                }
            }
            return;
        }
        solve(moveUp(map), depth + 1);
        solve(moveRight(map), depth + 1);
        solve(moveDown(map), depth + 1);
        solve(moveLeft(map), depth + 1);
    }

    private static int[][] moveLeft(int[][] map) {
        int[][] newMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            Stack<Integer> stack = new Stack<Integer>();
            int idx = N-1;
            for (int j = N-1; j >=0; j--) {
                if (map[i][j] == 0) continue;
                if(stack.isEmpty()) stack.push(map[i][j]);
                else{
                    if (stack.firstElement() == map[i][j]) {
                        newMap[i][idx--] = map[i][j] * 2;
                        stack.pop();
                    } else {
                        newMap[i][idx--] = stack.pop();
                        stack.push(map[i][j]);
                    }
                }
            }
            while (!stack.isEmpty()) {
                newMap[i][idx--] = stack.pop();
            }
        }
        return newMap;
    }

    private static int[][] moveDown(int[][] map) {
        int[][] newMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            Stack<Integer> stack = new Stack<Integer>();
            int idx = N-1;
            for (int j = N-1; j >=0; j--) {
                if (map[j][i] == 0) continue;
                if(stack.isEmpty()) stack.push(map[j][i]);
                else{
                    if (stack.firstElement() == map[j][i]) {
                        newMap[idx--][i] = map[j][i] * 2;
                        stack.pop();
                    } else {
                        newMap[idx--][i] = stack.pop();
                        stack.push(map[j][i]);
                    }
                }
            }
            while (!stack.isEmpty()) {
                newMap[idx--][i] = stack.pop();
            }
        }
        return newMap;
    }


    private static int[][] moveRight(int[][] map) {
        int[][] newMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            Stack<Integer> stack = new Stack<Integer>();
            int idx = 0;
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0) continue;
                if(stack.isEmpty()) stack.push(map[i][j]);
                else{
                    if (stack.firstElement() == map[i][j]) {
                        newMap[i][idx++] = map[i][j] * 2;
                        stack.pop();
                    } else {
                        newMap[i][idx++] = stack.pop();
                        stack.push(map[i][j]);
                    }
                }
            }
            while (!stack.isEmpty()) {
                newMap[i][idx++] = stack.pop();
            }
        }
        return newMap;
    }

    public static int[][] moveUp(int[][] map) {
        int[][] newMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            Stack<Integer> stack = new Stack<Integer>();
            int idx = 0;
            for (int j = 0; j < N; j++) {
                if (map[j][i] == 0) continue;
                if(stack.isEmpty()) stack.push(map[j][i]);
                else{
                    if (stack.firstElement() == map[j][i]) {
                        newMap[idx++][i] = map[j][i] * 2;
                        stack.pop();
                    } else {
                        newMap[idx++][i] = stack.pop();
                        stack.push(map[j][i]);
                    }
                }
            }
            while (!stack.isEmpty()) {
                newMap[idx++][i] = stack.pop();
            }
        }
        return newMap;
    }
}