[백준] 12100. 2048 (Easy)

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

12100번: 2048 (Easy)

• 상하좌우로 총 5번 움직였을 때 그래프에 있는 가장 큰 수를 구하는 문제이다. 따라서 상하좌우로 5번 움직이는 조합을 찾기 위해 재귀를 사용해야 한다.
• 그리고 상하좌우로 움직이는 로직을 구현해야 한다.
  • 기존 배열을 보고 새로운 배열을 만들어야 한다.
  • 새로운 배열에 값을 채울 인덱스인 fillIdx와 기존 배열과 값을 비교할 인덱스인 checkIdx가 필요하다.
  • 기존 배열의 값 num과 새로운 배열의 checkIdx번째 값이 같으면,
    • 수를 합쳐야하므로 checkIdx번째 값을 2배한다.
    • 해당 인덱스는 이미 한 번 합쳐졌으므로 다음에는 체크할 필요가 없다. 따라서 checkIdx의 값을 1 증가시키거나 감소시킨다.
  • 기존 배열의 값 num과 새로운 배열의 checkIdx번째 값이 같지 않으면,
    • fillIdx 위치에 num을 저장한다.
    • 값이 합쳐지지 않고 새로운 위치에 추가되었으므로 fillIdx의 값을 1 증가시키거나 감소시킨다.
    • checkIdx는 fillIdx보다 1 작거나 커야하므로 변경시킨다. 

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.*;

// 시간복잡도: 4^5 + O(N^2) (dfs + 그래프 탐색) = 4^5 + 400
public class Main {

    static int n;
    static int[][] map;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, copyMap(map));
        System.out.println(answer);
    }

    private static void dfs(int count, int[][] map) {
        if (count == 5) {
            answer = Math.max(getMax(map), answer);
            return;
        }

        // 위
        dfs(count + 1, up(copyMap(map)));

        // 아래
        dfs(count + 1, down(copyMap(map)));

        // 오른쪽
        dfs(count + 1, right(copyMap(map)));

        // 왼쪽
        dfs(count + 1, left(copyMap(map)));
    }

    private static int[][] up(int[][] map) {
        int[][] newMap = new int[n][n];
        for (int i = 0; i < n; i++) {
            int fillIdx = 0;
            int checkIdx = 0;
            for (int j = 0; j < n; j++) {
                int num = map[j][i];
                if (num == 0) continue;
                // 합치는 경우
                if (newMap[checkIdx][i] == num) {
                    newMap[checkIdx][i] = num * 2;
                    checkIdx++;
                }
                // 합치지 않는 경우
                else {
                    newMap[fillIdx][i] = num;
                    fillIdx++;
                    checkIdx = fillIdx - 1;
                }
            }
        }
        return newMap;
    }

    private static int[][] down(int[][] map) {
        int[][] newMap = new int[n][n];
        for (int i = 0; i < n; i++) {
            int fillIdx = n - 1;
            int checkIdx = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                int num = map[j][i];
                if (num == 0) continue;
                if (newMap[checkIdx][i] == num) {
                    newMap[checkIdx][i] = num * 2;
                    checkIdx--;
                } else {
                    newMap[fillIdx][i] = num;
                    fillIdx--;
                    checkIdx = fillIdx + 1;
                }
            }
        }
        return newMap;
    }

    private static int[][] right(int[][] map) {
        int[][] newMap = new int[n][n];
        for (int i = 0; i < n; i++) {
            int fillIdx = n - 1;
            int checkIdx = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                int num = map[i][j];
                if (num == 0) continue;
                if (newMap[i][checkIdx] == num) {
                    newMap[i][checkIdx] = num * 2;
                    checkIdx--;
                } else {
                    newMap[i][fillIdx] = num;
                    fillIdx--;
                    checkIdx = fillIdx + 1;
                }
            }
        }
        return newMap;
    }

    private static int[][] left(int[][] map) {
        int[][] newMap = new int[n][n];
        for (int i = 0; i < n; i++) {
            int fillIdx = 0;
            int checkIdx = 0;
            for (int j = 0; j < n; j++) {
                int num = map[i][j];
                if (num == 0) continue;
                if (newMap[i][checkIdx] == num) {
                    newMap[i][checkIdx] = num * 2;
                    checkIdx++;
                } else {
                    newMap[i][fillIdx] = num;
                    fillIdx++;
                    checkIdx = fillIdx - 1;
                }
            }
        }
        return newMap;
    }

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

    private static int[][] copyMap(int[][] map) {
        int[][] copy = new int[n][n];
        for (int i = 0; i < n; i++) {
            copy[i] = map[i];
        }
        return copy;
    }
}