백준 12100 - 2048 (Easy)

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

12100번: 2048 (Easy)

---

문제 분석

문제 자체는 굉장히 간단하다.
처음에 주어진 블록에서 5번을 움직여서 가장 큰 블록을 찾으면 된다.
주의점은 한 번 움직일 때 같은 칸에서 두 번 합쳐질 수 없으며,
이동하는 방향을 우선으로 합쳐야 한다.

 

왼쪽 블록을 위로 움직인 경우

위 그림을 예시로 보자.
왼쪽 블록들을 위쪽으로 움직인 경우의 결과에 대한 그림이다.

 

결과블록의 첫번째 열을 보면 4가 중복되었지만 합쳐지지 못했다.
왜냐하면 첫번째 행의 4는 2와 2가 한 번 합쳐져서 만들어졌기때문에 한 번 더 이상 합칠 수 없는 것이다.

또한 0은 빈칸으로 간주되어 무시하고 합쳐진 것을 알 수 있다.

 

초기블록의 두번째 열을 보면 4가 연달아서 세 번 나오고 있다.

그리고 결과블록을 보면 1행에 8, 2행에 4가 들어가고 있다.

이것은 이동하는 방향으로 먼저 합친다라는 조건에 의해 위쪽으로 먼저 합쳤기때문이다.

해당 조건을 고려하지 않는다면 2행의 4와 3행의 4가 합쳐질 수도 있다.
그러면 1행에 4, 2행에 8이 들어가게 될 것이다.

 

이 두가지 조건을 잘 고려해서 문제를 풀어야 한다.

---

내가 접근했던 방법

먼저 블록을 움직이는 메서드부터 살펴보자!

블록을 움직일 때 가장 먼저 고려했던 것은 '이동하는 방향으로 먼저 합친다'라는 조건이었다.

이를 위해서 가장 핵심적인 것은 시작점이라고 생각했다.

 

위로 움직이는 경우를 예로 들어 살펴보겠다.

2번째 행에서부터 아래로 내려간다면, 2번째 행에서 위쪽과 합쳐지는지 먼저 검사하기때문에 
이동방향으로 먼저 합치는 것이 가능하다.

즉, 우선순위가 높은 블록부터 검사하는 것이다.

 

이러한 것을 고려해봤을 때 각 움직임에 따라 다음과 같은 방향으로 로직을 진행해야 한다.

위로 움직일 때는 2번째 행부터 시작하여 하단 방향

아래로 움직일 때는 (N-1)번째 행부터 시작하여 상단 방향

왼쪽으로 움직일 때는 2번째 열부터 시작하여 우측 방향

오른쪽으로 움직일 때는 (N-1)번째 열부터 시작하여 좌측 방향

(N은 보드의 크기이다.)

이를 위해 시작방향을 다음과 같이 설정한다.

xyStart = new int[][]{{1, 0}, {N - 2, 0}, {0, 1}, {0, N - 2}};

 

우선순위가 높은 블록부터 검사하면 중복계산은 신경쓰지 않아도 될 것처럼 보이기도 한다.

블록 검사 후 합치는 게 불가능하면 다음 블록으로 넘어가주기만 하면 되니까 말이다.

 

하지만 여기에 0이 고려되기 시작하면 중복계산을 방지하기 위한 로직도 작성해줘야 한다.

움직일 위치의 숫자가 0이라면 현재 위치의 숫자를 옮겨주면 된다.

그런데 옮겨주기만 하면 끝일까?

(위치는 1부터 시작한다.)
1번 위치에서 2 0 2를 오른쪽으로 움직인다고 생각해보겠다. 0 2 2가 되었다.
이후 2번 위치에서 한 번 더 검사(로직 실행)해보면 0 0 4가 되는 것을 알 수 있다.

이번에는 4 0 2 2에서 오른쪽으로 움직이는 경우를 생각해보겠다.
오른쪽으로 움직이므로 시작점은(N - 1)인 3번 위치가 될 것이다.
3번 위치에서 움직이면 4 0 0 4가 된다.
그 후 2번은 0이므로 건너뛰고 1번에서 오른쪽으로 움직이면
0 4 0 4 -> 0 0 4 4가 된다. 그리고 이 때는 4가 2개지만 합칠 수 없다.
왜냐하면 4번의 4는 이미 가산되었기때문이다.

움직일 위치가 0이라서 숫자를 옮겨줬는데, 그 다음이 또 0이거나 합산이 가능할 수도 있다.

따라서 0을 만났다면 숫자를 옮겨준 후, 해당 위치를 한 번 더 검사해줘야 한다. 

또한 0에서부터 왔다면 다음 위치로 가서는 안 된다.

검사 시점에 서로 달라 가산이 안 되던 것이 블록을 움직이는 도중 가산이 되어 같아질 수 있다.
그리고 가산이 되어서 같아진 후에 한 번 더 검사하게 되면 다음 블록과 수가 같아 또 가산될 수가 있다.
이럴 경우 2번 이상의 가산이 이뤄질 수 있으므로 0에서부터 왔다면 다음 위치로 가서는 안 된다.

지금까지 살펴본 부분들을 의사코드로 살펴보면 다음과 같다.

블록검사(현재위치, 목표방향, 0에서 왔는지 여부)
    목표방향을 통해 현재위치로부터 목표위치 계산
    if(목표위치가 범위 밖 == true or 현재위치_계산여부 == true) return
    
    if 목표위치 == 0
        목표위치 = 현재위치
        현재위치 = 0
        블록검사(목표위치, 목표방향, true)
    if 현재위치 == 목표위치
        목표위치 += 현재위치
    	현재위치 = 0
        현재위치_계산여부 = true

	최댓값 = 현재위치와 최댓값 중 더 큰 값
	if(0에서 왔는지 여부 == true) return
    다음위치 계산
    if(다음위치 범위 밖 == true) return
    블록검사(다음위치, 목표방향, false)

 

그리고 이 블록을 검사하는(움직이는) 함수를 모든 방향으로 5번 움직여보면서 최댓값을 찾으면 된다.

---

최종코드

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

public class Main {
    static int MAX = 0, N;
    // 좌우상하
    static int xyMove[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, xyStart[][];
    static boolean calculated[][];

    // 백준 12100 - 2048 (Easy)
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        N = strToInt(bufferedReader.readLine());
        int data[][] = new int[N][N];
        calculated = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer token = new StringTokenizer(bufferedReader.readLine());
            for (int j = 0; j < N; j++) data[i][j] = strToInt(token.nextToken());
        }

        if(N == 1) {
            System.out.println(data[0][0]);
            return;
        }

        xyStart = new int[][]{{1, 0}, {N - 2, 0}, {0, 1}, {0, N - 2}};
        dfs(data, 0);
        System.out.println(MAX + "");
    }

    // 각 방향별로 이동을 발생시키는 함수
    private static void dfs(int[][] data, int len) {
        if (len == 5) return;

        int source[][] = new int[N][N];
        for (int i = 0; i < N; i++) source[i] = data[i].clone();
        for (int i = 0; i < 4; i++) {
            calculated = new boolean[N][N];
            blockMove(xyStart[i][1], xyStart[i][0], i, data, false);
            dfs(data, len + 1);
            for (int j = 0; j < N; j++) data[j] = source[j].clone();
        }
    }

    //입력받은 좌표를 기점으로 moveIdx에 따라 한 칸 움직이는 함수
    private static void blockMove(int y, int x, int moveIdx, int result[][], boolean fromZero) {
        int nextY = y + xyMove[moveIdx][1];
        int nextX = x + xyMove[moveIdx][0];
        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N || calculated[y][x]) return;

        // 블록 밀기
        int v1 = result[y][x], v2 = result[nextY][nextX];
        if (v2 == 0) {
            result[y][x] = 0;
            result[nextY][nextX] += v1;
            if(v1 != 0) blockMove(nextY, nextX, moveIdx, result, true);
        } else if (v1 == v2) {
            result[y][x] = 0;
            result[nextY][nextX] += v1;
            calculated[y][x] = true;
        }

        MAX = Math.max(MAX, result[x][y]);
        if(fromZero) return; //0에서 온 경우 다음 인덱스로 가는 것을 막는다.

        if (xyMove[moveIdx][0] == 0) {
            x++;
            if(x >= N) {
                x = 0;
                y += xyMove[moveIdx][1] * -1;
            }
        } else {
            y++;
            if(y >= N) {
                y = 0;
                x += xyMove[moveIdx][0] * -1;
            }
        }
        if (y < 0 || y >= N || x < 0 || x >= N) return;
        blockMove(y, x, moveIdx, result, false);
    }

    private static int strToInt(String str) {
        return Integer.parseInt(str);
    }
}