[백준 알고리즘] 12100번 자바(Java) 2048(Easy)

조건

 

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

 

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

풀이

기본적으로 2048의 상하좌우 이동에 대한 메서드는 아래 글을 참고하면 된다

https://developerjisu.tistory.com/120

[SWEA] 6109번 자바(Java) 추억의 2048게임

 

이제 추가해야할 부분은 5번 이동했을때의 최대값을 구하는 과정이다. 그 과정에서 배열 복사가 필요하고 이때 배열은 2단 배열이므로 깊은 복사가 필요하다. 깊은 복사의 내용은 아래와 같다.

• 1단 배열 복사: Arrays.clone();
• 2단 배열 복사: clone을 바로 해버리면 1단 배열들을 참조하는 2단 배열을 clone하는거다. 따라서 1단 배열들을 클론해줘서 2단 배열을 만들어야한다.

  private static int[][] deepCopy(int[][] original) {
        int[][] copy = new int[N][];
        for (int i = 0; i < N; i++) {
            copy[i] = original[i].clone();  // 각 행을 개별적으로 복사
        }
        return copy;
    }

 

이후에 deque의 값과 칸의 값이 더해질때 큰값이 나올수있기 때문에 중간에 max = Math.max(a, b)넣어준다. 추가로 처음 입력받은 값이 제일 클 수 있기때문에 max는 map값 입력받을때 제일 큰값으로 지정한다. 

 

 

추가 구현(최적화)

이 문제의 다음단계인 "2048(Hard)"를 풀기 위해 고민한 방법이다. 실제로는 시간초과로 통과하지는 못했지만 2048(Easy)의 실행시간은 줄였다. 움직여도 변하지않은 경우가 있다. 이제 좌우 한번씩 움직여도 동일한 맵과 상하 한번씩 움직여도 동일한 맵이있다. 그 경우를 판별하고자 flag를 4개 두고 상하, 또는 좌우가 둘다 false이면 return시켜 더이상 가지치가 작동하지 않도록 했다.

 

 

예제 입력 예시

3
2 2 2
4 4 4
8 8 8

 

예제 출력 예시

16

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

//12094번

public class Main {
    private static int N, max;
    private static boolean[] change; //상하좌우 변경된 경우 확인

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

        // map입력받기
        int[][] originalMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                originalMap[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(max, originalMap[i][j]);
            }
        }

        change = new boolean[4];
        Arrays.fill(change, true);
        perm(originalMap, 0);

        System.out.println(max);
    }

    private static void perm(int[][] map, int cnt) {
        if (cnt == 5) return;


        int[][] cloneMap1 = deepCopy(map);
        change[0] = false;
        play2048(cloneMap1, false, 0, N, 1, cnt, 0); //up
        change[0] = true;

        int[][] cloneMap2 = deepCopy(map);
        change[1] = false;
        play2048(cloneMap2, false, N - 1, -1, -1, cnt, 1); //down
        change[1] = true;

        int[][] cloneMap3 = deepCopy(map);
        change[2] = false;
        play2048(cloneMap3, true, N - 1, -1, -1, cnt, 2); //right
        change[2] = true;

        int[][] cloneMap4 = deepCopy(map);
        change[3] = false;
        play2048(cloneMap4, true, 0, N, 1, cnt, 3); //left
        change[3] = true;
    }

    private static int[][] deepCopy(int[][] original) {
        int[][] copy = new int[N][];
        for (int i = 0; i < N; i++) {
            copy[i] = original[i].clone();  // 각 행을 개별적으로 복사
        }
        return copy;
    }

    private static void play2048(int map[][], boolean goX, int s, int e, int m, int cnt, int changeNum) {
        int ys = 0;
        int xs = 0;
        if (goX) xs = s;
        else ys = s;

        while (!((goX) ? ys == N : xs == N)) {
            Deque<Integer> d = new LinkedList<>();
            boolean flag = false; //true면 이전에서 합쳐진경우
            if (goX) xs = s;
            else ys = s;

            while (!((goX) ? xs == e : ys == e)) {
                if (map[ys][xs] == 0) {
                } else if (d.isEmpty()) d.add(map[ys][xs]); // 비어있는 경우
                else if (flag || d.peekLast() != map[ys][xs]) { // 이전에서 합쳐진 경우 또는 현개값과 스택의 peek이 다른경우
                    d.add(map[ys][xs]);
                    flag = false;
                } else if (map[ys][xs] != 0) { //flag가 false이고 같은 경우
                    int num = d.pollLast()*2;
                    d.add(num);
                    max = Math.max(max, num);
                    flag = true;
                    change[changeNum] = true;
                }
                map[ys][xs] = 0;
                if (goX) xs += m;
                else ys += m;
            }

            if((!change[0]&&!change[1])||(!change[2]&&!change[3])) return;

            //빈칸 채워주기
            if (goX) {
                int xIdx = s;
                while (!d.isEmpty()) {
                    map[ys][xIdx] = d.poll();
                    xIdx += m;
                }
                ys++;
            } else {
                int yIdx = s;
                while (!d.isEmpty()) {
                    map[yIdx][xs] = d.poll();
                    yIdx += m;
                }
                xs++;
            }
        }

        perm(map, cnt + 1);
    }
}

 

 

 

 

문제 출처

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