[백준 #12100 c++] 2048 easy

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

12100번: 2048 (Easy)

 

이 문제를 처음 푼게 3년전이었고 그 때는 한 3일간 고군분투했지만 끝내 통과하지 못했다.

질문 게시판에 존재하는 모든 테스트케이스를 통과했음에도 '틀렸습니다'가 나오는 이유는 아직도 모르겠다.

 

3년이 지난 지금 다시 풀어보았고 역시나 쉽지 않은 문제였다.

때문에 다른 사람이 푼 코드를 참고하여 풀었다.

 

참고한 코드:
https://bio-info.tistory.com/230

 

 

문제의 유형은 그냥 어떤 정답이 존재한다기 보다는 빡구현에 가깝다.

하지만 N-Queen 문제처럼 빨리 푸는 로직이 분명 존재하며 그것을 위해 문제의 기본 로직을 풀어서 설명해보자.

 

로직 파헤치기

숫자가 이동하는 과정 (왼쪽 방향)

위의 숫자를 왼쪽으로 이동시키면 어떻게 될까?

 

왼쪽의 4 두 개가 합쳐지고 오른쪽 끝 4가 가운데로 온다.

 

이동 방향에 있는 숫자가 먼저 합쳐지며

이동 과정에서 빈 공간이 존재하면 채워진다.

 

 

그럼 이건 왼쪽으로 몰면 어떻게 될까?

 

왼쪽의 4는 그대로 있고 2 두 개가 합쳐져서 가운데에 남게 된다.

2는 이미 합쳐졌기 때문에 더 합쳐질 수 없으므로 왼쪽의 4와 합쳐지지 않고 그대로 남아있는 것이다.

 

이렇게 게임 로직의 핵심을 살펴보았고 다시 이것들을 쪼개서 코드로 구현할 수 있을 정도로 해보자.

 

 

숫자가 이동하는 과정 하나씩 보기 (왼쪽 방향)

 

하나의 숫자가 처한 상황은 다음 세 가지가 있다.

 

1. 빈 칸으로 이동하는 경우

 

 

2. 합쳐지는 경우

 

 

3. 이동이 불가능한 경우

 

 

숫자가 이동 또는 합치기가 가능한 경우

목표위치의 값을 변경(2배로 하거나, 값을 채우거나)하게 된다.

 

하지만 이동이 불가능한 경우에는 아무일도 일어나지 않는다.

 

그러면 코드 내부적으로는 어떤 처리가 필요할까?

---

가운데의 숫자 2를 4가 있는 자리로 이동시키고 싶다.

목표위치는 1이고 현재위치는 2이다.

 

하지만 2를 이동시킬 수 없다.

그러므로 목표위치에 있는 4는 앞으로도 변경 되지 않을 것임을 알 수 있고

목표위치와 현재위치 둘 다 뒤로 한 칸 옮기면 될 것 같다는 생각이 든다.

 

이렇게 하면 다음 과정은 자연스럽게 예상이 된다.

목표위치에 현재위치에 있는 2를 합쳐버리는 것이고

현재위치를 비워주는 것이다.

(그림 생략)

 

---

이동이 불가능한 경우의 처리를 알아봤으니

이제 이동이 가능한 경우에서도 목표위치와 현재위치를 사용할 수 있는지 보자.

 

현재위치에 있는 4는 목표위치에 있는 4와 합쳐질 수 있다.

합치고 난 다음에는 가운데 4 자리가 빌 것이고 그 다음 자리에 있는 2가 이동할 수 있을 것이다.

 

다음 턴에 2를 이동시키기 위해서는

목표위치를 두 번째, 현재위치를 세 번째로 옮기는 것이 현명해보인다.

과연 그런가 한 번 보자.

 

합쳐진 8은 더 이상 이동할 수 없으므로 목표위치를 옮기는 것은 맞다고 보인다.

그리고 빈 칸이 되버린 가운데는 이동할 숫자가 없으므로 현재위치 역시 한 칸 뒤로 옮기는 것도 좋아 보인다.

 

---

멀리 떨어진 숫자가 합쳐지는 경우는 어떨까?

 

우선 현재위치가 빈 칸이므로 현재위치를 뒤로 한 칸 보내보자.

 

이제 현재위치에 있는 2를 목표위치의 2에게 합칠 수 있는 상황이 되었다.

그리고 합쳐진 4는 더이상 합쳐질 수 없으므로 목표위치를 한 칸 뒤로 보낼 수 있고

현재위치는 빈 칸이 되었으므로 현재위치 역시 한 칸 뒤로 보낼 수 있어 보인다.

 

---

다음 경우를 보자

 

목표위치가 비어있으므로 현재위치의 4를 이동시킬 수 있다.

그렇게 이동한 4는 아직 합쳐진 적이 없으므로 목표위치를 옮기면 안된다.

 

현재위치만 뒤로 한 칸 옮겨주면 된다.

 

 

지금까지 목표위치와 현재위치라는 포인터를 두면서 숫자를 옮기는 예시를 살펴보았다.

이를 토대로 우리는 숫자의 배치 상황에 따라 어떻게 포인터를 옮겨야 하는지 정리해보면,

 

1. 현재위치가 빈 칸이면 현재위치를 뒤로 한 칸 옮긴다.

2. 목표위치가 빈 칸이면 목표위치로 숫자를 옮기고 현재위치를 뒤로 한 칸 옮긴다.

3. 목표위치와 숫자가 합쳐질 수 있으면 숫자를 합치고 목표위치와 현재위치를 뒤로 한 칸 옮긴다.

4. 숫자가 이동할 수 없다면 목표위치와 현재위치를 뒤로 한 칸 옮긴다.

 

여기서 현재위치는 모든 경우에 뒤로 옮길 수 있으므로 별도의 예외처리가 필요하진 않지만

목표위치의 경우 예외처리가 필요하다는 것을 알 수 있다.

 

 

 

문제를 풀기 위한 과정은 다음으로 요약될 수 있다.

 

1. 문제의 유형을 분석한다.

• 완전탐색 구현이다. 숫자판의 최대 길이가 20이고 이동 횟수가 5이므로 시간복잡도가 매우 적고 모든 배열을 복사하는 공간복잡도 역시 크게 문제될 부분이 없으므로 완전탐색이 가능하다.

2. 게임의 로직을 파악한다.

• 숫자가 움직이는 방식을 살펴본다.

3. 로직을 어떻게 코드화할 수 있는지 문제의 유형을 다시 생각해본다.

• 투포인터를 두어서 배열에 접근하고 숫자들의 순차적인 이동을 고려해본다.

4. 코드로 옮긴다.

 

 

 

// BOJ GOLD 2
// https://www.acmicpc.net/problem/12100

#include <bits/stdc++.h>

int n;
int Max;

void move(int board[][21], int dir) {
    if (dir == 0) { // LEFT
        for (int i = 1; i <= n; i++) {
            int idx = 1;
            for (int j = 2; j <= n; j++) {
                if (board[i][j] == 0) continue; // 현재 칸이 빈 칸인 경우 다음 칸으로
                int from = board[i][j];
                board[i][j] = 0;
                int* to = &board[i][idx];
                
                if (*to == 0) {
                    *to = from; // 빈 칸으로 이동
                }
                else if (*to == from) {
                    *to *= 2; // 합치기
                    idx++; // 한 번 합쳐진 후에는 다시 합쳐지지 않도록 목표지점 이동
                }
                else {
                    idx++; // 이동과 합치기가 불가능한 경우 목표지점 이동
                    board[i][idx] = from; // 목표지점으로 숫자 이동 (두 숫자가 붙어있는 경우에는 복원에 해당됨)
                }
            }
        }
    }
    else if (dir == 1) { // RIGHT
        for (int i = 1; i <= n; i++) {
            int idx = n;
            for (int j = n - 1; j > 0; j--) {
                if (board[i][j] == 0) continue; // 현재 칸이 빈 칸인 경우 다음 칸으로
                int from = board[i][j];
                board[i][j] = 0;
                int* to = &board[i][idx];

                if (*to == 0) {
                    *to = from; // 빈 칸으로 이동
                }
                else if (*to == from) {
                    *to *= 2; // 합치기
                    idx--; // 한 번 합쳐진 후에는 다시 합쳐지지 않도록 목표지점 이동
                }
                else {
                    idx--; // 이동과 합치기가 불가능한 경우 목표지점 이동
                    board[i][idx] = from; // 목표지점으로 숫자 이동 (두 숫자가 붙어있는 경우에는 복원에 해당됨)
                }
            }
        }
    }
    else if (dir == 2) { // UP
        for (int j = 1; j <= n; j++) {
            int idx = 1;
            for (int i = 2; i <= n; i++) {
                if (board[i][j] == 0) continue; // 현재 칸이 빈 칸인 경우 다음 칸으로
                int from = board[i][j];
                board[i][j] = 0;
                int* to = &board[idx][j];

                if (*to == 0) {
                    *to = from; // 빈 칸으로 이동
                }
                else if (*to == from) {
                    *to *= 2; // 합치기
                    idx++; // 한 번 합쳐진 후에는 다시 합쳐지지 않도록 목표지점 이동
                }
                else {
                    idx++; // 이동과 합치기가 불가능한 경우 목표지점 이동
                    board[idx][j] = from; // 목표지점으로 숫자 이동 (두 숫자가 붙어있는 경우에는 복원에 해당됨)
                }
            }
        }
    }
    else if (dir == 3) { // DOWN
        for (int j = 1; j <= n; j++) {
            int idx = n;
            for (int i = n - 1; i > 0; i--) {
                if (board[i][j] == 0) continue; // 현재 칸이 빈 칸인 경우 다음 칸으로
                int from = board[i][j];
                board[i][j] = 0;
                int* to = &board[idx][j];

                if (*to == 0) {
                    *to = from; // 빈 칸으로 이동
                }
                else if (*to == from) {
                    *to *= 2; // 합치기
                    idx--; // 한 번 합쳐진 후에는 다시 합쳐지지 않도록 목표지점 이동
                }
                else {
                    idx--; // 이동과 합치기가 불가능한 경우 목표지점 이동
                    board[idx][j] = from; // 목표지점으로 숫자 이동 (두 숫자가 붙어있는 경우에는 복원에 해당됨)
                }
            }
        }
    }
}

void dfs(int board[][21], int num) {
    if (num == 0) return;

    for (int i = 0; i < 4; i++) {
        int tboard[21][21];
        memset(tboard, 0, sizeof(tboard));
        memcpy(tboard, board, sizeof(tboard));
        move(tboard, i);
        Max = std::max(Max, *std::max_element(&tboard[1][1], &tboard[n][n + 1]));

        dfs(tboard, num - 1);
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0);

    int board[21][21];
    memset(board, 0, sizeof(board));
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cin >> board[i][j];
        }
    }

    dfs(board, 5);
    std::cout << Max;

    return 0;
}