[알고리즘] 2048

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static class Point {
        int value;
        boolean isStop;

        public Point(int value, boolean isStop) {
            this.value = value;
            this.isStop = isStop;
        }

        public Point(Point point) {
            this.value = point.value;
            this.isStop = false;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "value=" + value +
                    ", isStop=" + isStop +
                    '}';
        }
    }

    static int n;
    static int[][] map;
    static int[][] tempMap;
    static List<int[]> dirs;
    static int[] tempDir;
    static int[][] originalMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        originalMap = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                originalMap[i][j] = map[i][j];
            }
        }
        dirs = new ArrayList<>();
        tempDir = new int[5];
        recursive(0);

        int resultMax = Integer.MIN_VALUE;
        for (int[] dir : dirs) {
            copyMap();
            for (int i = 0; i < 5; i++) {
                move(dir[i]);
            }
            resultMax = Math.max(resultMax, findMaxValue());
        }
        System.out.println(resultMax);
//        move(0);
//        print();
    }

    private static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = originalMap[i][j];
            }
        }
    }

    private static int findMaxValue() {
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxValue = Math.max(maxValue, map[i][j]);
            }
        }
        return maxValue;
    }

    private static void recursive(int depth) {
        if (depth == 5) {
            dirs.add(Arrays.copyOfRange(tempDir, 0, tempDir.length));
            return;
        }

        for (int i = 0; i < 4; i++) {
            tempDir[depth] = i;
            recursive(depth+1);
        }
    }

    private static void move(int dir) {
        // 상하좌우
        Deque<Point>[] deque = new ArrayDeque[n];
        for (int i = 0; i < n; i++) {
            deque[i] = new ArrayDeque<>();
        }
        switch (dir) {

            case 0: // 상
                up(deque);
                gravity(deque);
                toMapUp(deque);
//                print();
                break;
            case 1: // 하
                down(deque);
                gravity(deque);
                toMapDown(deque);
//                print();
                break;
            case 2: // 좌
                left(deque);
                gravity(deque);
                toMapLeft(deque);
//                print();
                break;
            case 3: // 우
                right(deque);
                gravity(deque);
                toMapRight(deque);
//                print();
                break;
        }

    }

    private static void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    private static void toMapLeft(Deque<Point>[] deque) {
        tempMap = new int[n][n];
        for (int r = 0; r < n; r++) {
            int cnt = 0;
            while (!deque[r].isEmpty()) {
                Point point = deque[r].pollFirst();
                tempMap[r][cnt++] = point.value;
            }
        }
        map = tempMap;
    }

    private static void toMapRight(Deque<Point>[] deque) {
        tempMap = new int[n][n];
        for (int r = 0; r < n; r++) {
            int cnt = n - 1;
            while (!deque[r].isEmpty()) {
                tempMap[r][cnt--] = deque[r].pollFirst().value;
            }
        }
        map = tempMap;
    }

    private static void toMapUp(Deque<Point>[] deque) {
        tempMap = new int[n][n];
        for (int c = 0; c < n; c++) {
            int cnt = 0;
            while (!deque[c].isEmpty()) {
                tempMap[cnt++][c] = deque[c].pollFirst().value;
            }
        }
        map = tempMap;
    }
    private static void toMapDown(Deque<Point>[] deque) {
        tempMap = new int[n][n];
        for (int c = 0; c < n; c++) {
            int cnt = n - 1;
            while (!deque[c].isEmpty()) {
                tempMap[cnt--][c] = deque[c].pollFirst().value;
            }
        }
        map = tempMap;
    }
    private static void gravity(Deque<Point>[] deque) {
        Deque<Point>[] temp = new ArrayDeque[n];
        for (int i = 0; i < n; i++) {
            temp[i] = new ArrayDeque<>();
        }
        for (int i = 0; i < n; i++) {
            while (!deque[i].isEmpty()) {
                if (temp[i].isEmpty()) {
                    temp[i].add(new Point(deque[i].pollFirst()));
                } else {
                    Point point = temp[i].peekLast();
                    Point curPoint = deque[i].pollFirst();
                    if (!point.isStop) {
                        if (point.value == curPoint.value) {
                            point.value *= 2;
//                            System.out.println("point.value = " + point.value);
                            point.isStop = true;
                        } else {
                            temp[i].add(new Point(curPoint));

                        }
                    } else {
                        temp[i].add(new Point(curPoint));
                    }
                }
            }
            deque[i] = temp[i];
        }
    }

    private static void left(Deque<Point>[] deque) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (map[r][c] == 0) {
                    continue;
                }
                deque[r].add(new Point(map[r][c], false));
            }
        }
    }

    private static void right(Deque<Point>[] deque) {
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (map[r][c] == 0) {
                    continue;
                }
                deque[r].addFirst(new Point(map[r][c], false));
            }
        }
    }

    private static void up(Deque<Point>[] deque) {
        for (int c = 0; c < n; c++) {
            for (int r = 0; r < n; r++) {
                if (map[r][c] == 0) {
                    continue;
                }
                deque[c].add(new Point(map[r][c], false));
            }
        }
    }
    private static void down(Deque<Point>[] deque) {
        for (int c = 0; c < n; c++) {
            for (int r = 0; r < n; r++) {
                if (map[r][c] == 0) {
                    continue;
                }
                deque[c].addFirst(new Point(map[r][c], false));
            }
        }
    }
}

나의 풀이

- 미로 게임과 유사

- 맵에 있는 정보를 Deque으로 옮기고 각각에 이미 합쳐졌는지를 나타내는 isStop을 넣었다.

- 그리고 또 하나의 Deque(사실상 Stack으로 사용)을 이용하여 같으면 2배 다르면 넣어주기를 반복한다. 

- if (map[r][c] == 0)에서 break를 했는데 그렇게 되면 0 이후에 나오는 1 이상의 값이 무시되기 때문에 continue로 해주어야 한다.