백준 12094 - 2048(Hard)

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

12094번: 2048 (Hard)

보드 움직이기

먼저 보드를 움직이는 로직을 살펴보겠다.
간단하게 위로 움직이는 로직만 살펴본다.

private static boolean move(Direction dir, int cnt) {
        int[][] map = maps[cnt];
        boolean isChanged = false;

        switch (dir) {
            case TOP:
                for (int j = 0; j < N; j++) {
                    int target = 0;
                    for (int i = 1; i < N; i++) {
                        if (map[i][j] != 0) {
                            if (map[target][j] == map[i][j]) {
                                isChanged = true;
                                map[target][j] *= 2;
                                map[i][j] = 0;
                                MAX = Math.max(MAX, map[target++][j]);
                            } else {
                            	//target은 0이 아닐 때만 증가
                                if (map[target][j] != 0) target++;
                                if (map[target][j] == 0) {
                                    isChanged = true;
                                    map[target][j] = map[i][j];
                                    map[i][j] = 0;
                                }
                            }
                        }
                    }
                }
                break;
                //생략...
        }
}

1. for문의 중첩

보드를 움직일 때 for문을 보면, for문이 중첩되어있다.
또한 내부에 행을 위한 for문이 있고, 외부에 열을 위한 for문이 위치한다.
이는 열 하나를 위로 움직이는 것을 끝마친 후 다음 열로 넘어가기 위해서 열을 위한 for문을 바깥에 두는 것이다.
아래로 움직일 때도 마찬가지이다.

하지만 좌우로 움직일 때는 행하나를 먼저 좌우로 움직이는 것을 끝마친 후 다음 행으로 넘어가야하기때문에
외부에 행을 위한 for문을 두고, 내부에 열을 위한 for문을 둔다.

 

2. target의 용도

쉽게 말하면 target은 목적지이다.
(상하로 움직일 때 target은 목적행이 되고, 좌우로 움직일 때는 목적열이 된다.)

target을 따로 설정하는 이유는 목적행은 항상 증가하지 않고 특정 상황에서만 증가하기때문이다.
위로 움직일 때 최초 target(목적행)은 가장 첫 행인 0이 된다.
열을 탐색 중 0이 아닌 수를 만나는 경우 target과 같은지 확인하고, 같으면 2배로 만든다.
같지 않고, target이 0도 아니라면 target을 1 증가시킨다.

그 후 1 증가한 target이 0이라면 해당 위치로 탐색한 숫자를 옮긴다.

 

target이 0이라고 가정해보자!
0이 아닌 숫자를 만나도 else문에서  target은 증가하지 않고,  그 숫자를 첫 행으로 당겨온다.
(target은 0이 아닐 때만 증가하기때문이다 > 주석 참고)
이번에는 첫 행이 2라고 가정하고, 4번째 행이 4라고 가정해보자!
4번째 행에서 4를 만나도 첫 행의 값인 2와 같지 않기때문에 서로 합쳐지지 않고, else문으로 진입한다. 
또한 첫 행의 값이 2로 0이 아니기때문에 target이 1 증가한다.
그리고 두 번째 행으로 4가 당겨지게 된다.

 

target이 특정상황에서만 증가한다고 했다.
이 특정상황을 정리하면 "해당 블록이 한 번이라도 0이 아닌 다른 숫자와 비교되었는가?"가 된다.
비교 후 숫자가 같아서 한 번 합치거나, 달라서 합칠 수 없는 경우에만 target은 증가할 수 있는 것이다.
이런 이유로 target은 항상 증가시키지 않고 비교가 완료된 후에만 증가시키는 것이다.
(상하좌우 방향에 따라 target을 감소시키기도 한다)

 

3. MAX 값찾기

MAX는 숫자가 동일해서 서로 합쳐지는 경우에만, 검사하면 된다.

---

DFS 탐색 & 백트래킹

보드를 움직일 수 있게 되었으니 이제 DFS탐색을 해야 한다.

private static void dfs(Direction dir, int cnt) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            maps[cnt][i][j] = maps[cnt - 1][i][j];
        }
    }
    boolean isChanged = move(dir, cnt);

    if (!isChanged || cnt == 10) {
        return;
    }

    cnt++;
    for (Direction d : Direction.values()) {
        dfs(d, cnt);
    }
}

dfs() 함수는 Direction을 바꿔가면서 dfs()함수를 다시 호출한다.
그리고 board를 10번 움직였을 때 탐색을 멈춘다.
혹은 보드가 변하지 않은 경우 탐색을 멈춘다 > 백트래킹
보드가 변하지 않는 경우에는 최대값이 바뀔 가능성이 아예 존재하지 않는다.
보드가 변하는 경우에만 최대값이 바뀔 가능성이 존재한다.
따라서 보드가 변하지 않는 경우에는 탐색을 멈추는 것이다.

 

DFS 탐색을 할 때 3차원 배열인 maps를 이용한다.
maps[cnt]에 maps[cnt - 1]을 복사한다.
그리고 move() method에서는 이 maps[cnt] 보드를 움직인다.
쉽게 설명하면 maps[cnt]는 cnt번째의 보드 상황을 뜻한다.
예를 들면 maps[0]은 보드를 전혀 움직이지 않았을 때의 상태이고,
maps[1]은 보드를 한 번 움직였을 때의 상태이다.

 

동작 설명

그렇게 dfs(Direction.TOP, 9)에 도달했다고 하자!
내부 동작을 살펴보면 for문에 의해 dfs(Direction.TOP, 10)을 호출한다.
그러면 maps[9]를 기반으로 10번 움직인 board를 완성하게 되고
다시 호출했던 dfs()의 for문으로 돌아와서 dfs(Direction.BOTTOM, 10)을 호출한다.
이를 반복하여 상하좌우를 다 움직이면 dfs(Direction.TOP, 9)는 자신을 호출했던 dfs()함수로
거슬러 올러가게 되고 그 함수의 for문에 의해 dfs(Direction.BOTTOM, 9)가 호출되게 된다.

 

이렇게 3차원 배열을 이용해 코드를 작성한 이유는 메모리를 아끼기 위해서이다.
만약 dfs() 함수에서 파라미터로 2차원배열을 받고,
다시 dfs() 함수를 호출할 때 이 2차원 배열을 복사하는 식으로 코드를 작성하면 굉장히 많은 메모리가 사용된다.
이를 방지하기 위해 3차원 배열을 사용한다.