[백준 JAVA] 12100 2048 (Easy)

12100 2048 (Easy)

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

문제설명

주어진 n x n 격자에 숫자가 배치되어 있고, 사용자는 숫자를 이동시키는 방향을 선택하여

합쳐질 수 있는 숫자를 더해나가며 최대 숫자를 만들려고 한다.

숫자는 상하좌우로 이동할 수 있으며, 같은 숫자가 만나면 합쳐지고 새로운 숫자가 생성된다.

목표는 여러 번의 이동 후 격자에서 가장 큰 숫자를 찾는다.

접근방식

DFS를 사용해 각 조합에 대해 격자를 한 번씩 순회하므로 O(n^2)의 시간복잡도를 가진다.

•  

문제 조건 분석 과정

• DFS를 통한 방향 조합 생성:
  • 4가지 방향(상, 우, 하, 좌) 중에서 5번의 이동 방향을 선택하는 모든 조합을 생성하기 위해
  • DFS(Depth First Search)를 사용한다. 방향은 0, 1, 2, 3으로 각각 상, 우, 하, 좌를 나타낸다.
• 이동 및 합치기:
  • 선택된 방향으로 격자를 순회하며 이동 및 합치기를 진행한다.
  • move() 메소드를 사용하여 숫자를 이동시키고, 같은 숫자가 만났을 때 합치는 로직을 구현한다.
• 최대 숫자 찾기:
  • 모든 이동이 완료된 후, 격자에서 가장 큰 숫자를 찾아 max에 저장한다.
  • 모든 조합을 확인한 후 최댓값을 출력한다.

전체코드

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

public class Main {
    private static int n;
    private static int[][] map;
    private static int[][] temp;
    private static int[] direct;
    private static boolean[][] visit;

    private static int max = 0;

    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

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

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

        dfs(5, 0);
        System.out.println(max);
    }

    private static void dfs(int end, int index) {
        if (index == end) {
            confirm();
        } else {
            for (int i = 0; i < 4; i++) {
                direct[index] = i;
                dfs(end, index + 1);
            }
        }
    }

    private static void confirm() {
        temp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            temp[i] = map[i].clone();
        }

        for (int d = 0; d < direct.length; d++) {
            visit = new boolean[n+1][n+1];
            if (direct[d] == 0) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        move(i, j, direct[d]);
                    }
                }
            } else if (direct[d] == 2) {
                for (int i = n; i >= 1; i--) {
                    for (int j = 1; j <= n; j++) {
                        move(i, j, direct[d]);
                    }
                }
            } else if (direct[d] == 1) {
                for (int i = n; i >= 1; i--) {
                    for (int j = 1; j <= n; j++) {
                        move(j, i, direct[d]);
                    }
                }
            } else {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        move(j, i, direct[d]);
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (temp[i][j] > max) {
                    max = temp[i][j];
                }
            }
        }
    }

    private static void move(int x, int y, int dir) {
        if (temp[x][y] == 0) {
            return;
        }

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

            if (nx < 1 || ny < 1 || nx > n || ny > n) {
                return;
            }
            if (visit[nx][ny]) {
                return;
            }
            if (temp[nx][ny] == temp[x][y]) {
                visit[nx][ny] = true;
                temp[nx][ny] *= 2;
                temp[x][y] = 0;
                return;
            } else if (temp[nx][ny] != 0) {
                return;
            }

            temp[nx][ny] = temp[x][y];
            temp[x][y] = 0;
            x = nx;
            y = ny;
        }
    }
}