12100 백준 문제풀이 완료

package src.Week15.p12100;

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

public class Main {

    static int n, answer, map[][], copy[][];
    static int[] direct;
    static boolean[][] visit;
    static int[] dx = {0, -1, 0, 1}; // 우, 상, 좌, 하
    static int[] dy = {1, 0, -1, 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];
        direct = new int[5];

        StringTokenizer st;

        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());
            }
        }

        game(5, 0);
        System.out.println(answer);
    }

    public static void game(int end, int count) {
        if (count == end) {
            confirm();
            return;
        }

        for (int i = 0; i < 4; i++) {
            direct[count] = i;
            game(end, count + 1);
        }
    }

    public static void confirm() {
        // 원본 배열을 복사하여 이동 시도
        copy = new int[n][n];
        for (int i = 0; i < n; i++)
            copy[i] = map[i].clone();

        // 지정된 방향으로 이동 수행
        for (int d = 0; d < direct.length; d++) {
            visit = new boolean[n][n];
            moveBoard(direct[d]); // 방향에 따라 보드 이동
        }

        // 이동 후 최대값 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer = Math.max(answer, copy[i][j]);
            }
        }
    }

    public static void moveBoard(int dir) {
        // 각 방향에 맞게 블록을 이동시킴
        switch (dir) {
            case 0: // 우
                for (int i = 0; i < n; i++) {
                    for (int j = n - 1; j >= 0; j--) {
                        move(i, j, dir);
                    }
                }
                break;
            case 1: // 상
                for (int j = 0; j < n; j++) {
                    for (int i = 0; i < n; i++) {
                        move(i, j, dir);
                    }
                }
                break;
            case 2: // 좌
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        move(i, j, dir);
                    }
                }
                break;
            case 3: // 하
                for (int j = 0; j < n; j++) {
                    for (int i = n - 1; i >= 0; i--) {
                        move(i, j, dir);
                    }
                }
                break;
        }
    }

    public static void move(int x, int y, int dir) {
        if (copy[x][y] == 0) return;

        while (true) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n) return; // 범위 벗어나면 종료

            if (visit[nx][ny]) return; // 이미 합쳐진 블록이면 종료

            if (copy[nx][ny] == 0) { // 빈 공간으로 이동
                copy[nx][ny] = copy[x][y];
                copy[x][y] = 0;
                x = nx;
                y = ny;
            } else if (copy[nx][ny] == copy[x][y]) { // 같은 값이 있으면 합침
                visit[nx][ny] = true; // 합쳐졌음을 표시
                copy[nx][ny] *= 2;
                copy[x][y] = 0;
                return;
            } else {
                return; // 다른 값이 있는 경우 더 이동하지 않음
            }
        }
    }
}