[백준] 12100: 2048(Easy) (with C++)

엄청 어렵지는 않았지만 조건을 잘못 줘서 디버깅을 좀 하느라 시간을 많이 썼다. 문제 자체가 BFS + 각 가능한 노드 계산(꽤 양이 된다.) 문제여서 시간이 초과될까봐 조마조마했다. 다행히 시간초과는 나지 않았다.

예전에 프로그래밍 연습이라는 과목에서 2048 게임 만들기를 파이널 프로젝트로 했었는데 그때 생각도 나고 좋았다. 시간이 참 빠른 것 같다. 그 때가 불과 2년 반 전인데, 그땐 c++도 모르고 BFS도 모르는 비전공자 인문대생이였던 내가 벌써 컴퓨터공학 전공자로 곧 졸업을 하게 된다.

 

참고로 나는 이 문제에 2시간 20분을 썼다. 디버깅 때문이다. 한번 풀 때 제대로 풀어야 한다. 다행히 다음번에 푼 문제를 40분만에 후다닥 풀어서 통과했다. 실전이 아닌데도 정말 심장 쫄리는 경험이었다.

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

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

12100번: 2048 (Easy)

구상

(메모에 썼던 내용이다. 설명이 빈약할 수 있음)

1. BFS. 탐색 종료조건은 깊이 5 초과, 움직임 없음. 종료시 max 숫자 저장

2. 큐 설정, 현재 보드 상태와 움직인 횟수 저장

3. 큐의 front에 대해 각 이동방향으로 스와이프했을 때 결과가 종료조건이 아니면 큐에 저장, 종료조건이면 max저장

4. 큐가 비면 max 리턴

 

이렇게까지만 쓰고 내가 간과한 것이 한번의 이동에 한번만 합쳐질 수 있다는 조건이었다. 

[주의사항]

1. 한번 합쳐진 블록은 합쳐졌다는 사실을 저장해서 다른 블록과 합쳐지지 못하게 해야 한다.

 

위 조건까지 고려하면 이동 함수는 이렇게 짜면 된다.

1. 블럭들의 움직임이 있는 동안,

2. 이동 방향에 0이 있는 경우 0 자리를 대체한다. 이 때, 합쳐졌는지 정보도 블록과 함께 이동한다.

3. 이동 방향에 같은 숫자를 가졌으면서 합쳐진 이력이 없는 블럭이 있는 경우(당연히 지금 보고 있는 내 블럭도 합쳐진 이력이 없어야 한다.) 그 블럭의 숫자를 *2하고, 내 블럭은 0으로 없앤다. 이 때, *2한 블럭은 합쳐졌다고 표시한다.

4. 2, 3의 경우가 아니면 그대로 둔다.

5. 블럭 움직임이 있는 동안 2-4를 반복한다.

 

그렇게 짠 코드가 아래와 같다. 난 정말 말로 풀어 설명하는걸 잘 못하는 것 같다. 이해가 안되는 부분이 있으면 꼭 댓글에 남겨줬으면 좋겠다. 누가 보고 있는지는 모르겠지만...

#include<iostream>
#include<queue>
#include<climits>

using namespace std;

int find_max(int** board, int n) {
    int max = -1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j] > max) {
                max = board[i][j];
            }
        }
    }
    return max;
}

int** move(int** board, int n, int direction) {
    int** result;
    int** combined;
    result = new int*[n];
    combined = new int*[n];
    bool changed = false;
    
    for(int i=0; i<n; i++) {
        result[i] = new int[n];
        combined[i] = new int[n];
        for(int j=0; j<n; j++) {
            result[i][j] = board[i][j];
            combined[i][j] = 0;
        }
    }

    if(direction == 0) {
        //up
        bool moved = true;
        while(moved==true) {
            moved = false;
            for(int i=1; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(result[i][j] != 0 && result[i-1][j] == 0) {
                        result[i-1][j] = result[i][j];
                        combined[i-1][j] = combined[i][j];
                        combined[i][j] = 0;
                        result[i][j] = 0;
                        moved = true;
                    }
                    else if(result[i][j] != 0 && combined[i][j] == 0 && result[i-1][j] == result[i][j] && combined[i-1][j] == 0) {
                        result[i-1][j] = 2*result[i][j];
                        result[i][j] = 0;
                        combined[i-1][j] = 1;
                        moved = true;
                    }
                    else {
                        result[i][j] = result[i][j];
                    }
                }
            }
        }
    }
    else if (direction == 1) {
        //down
        bool moved = true;
        while(moved==true) {
            moved = false;
            for(int i=n-2; i>=0; i--) {
                for(int j=0; j<n; j++) {
                    if(result[i][j] != 0 && result[i+1][j] == 0) {
                        result[i+1][j] = result[i][j];
                        combined[i+1][j] = combined[i][j];
                        combined[i][j] = 0;
                        result[i][j] = 0;
                        moved = true;
                    }
                    else if(result[i][j] != 0 && combined[i][j] == 0 && result[i+1][j] == result[i][j] && combined[i+1][j] == 0) {
                        result[i+1][j] = 2*result[i][j];
                        result[i][j] = 0;
                        combined[i+1][j] = 1;
                        moved = true;
                    }
                    else {
                        result[i][j] = result[i][j];
                    }
                }
            }
        }
    }
    else if (direction == 2) {
        //right
        bool moved = true;
        while(moved==true) {
            moved = false;
            for(int i=0; i<n; i++) {
                for(int j=n-2; j>=0; j--) {
                    if(result[i][j] != 0 && result[i][j+1] == 0) {
                        result[i][j+1] = result[i][j];
                        combined[i][j+1] = combined[i][j];
                        combined[i][j] = 0;
                        result[i][j] = 0;
                        moved = true;
                    }
                    else if(result[i][j] != 0 && combined[i][j] == 0 && result[i][j+1] == result[i][j] && combined[i][j+1] == 0) {
                        result[i][j+1] = 2*result[i][j];
                        result[i][j] = 0;
                        combined[i][j+1] = 1;
                        moved = true;
                    }
                    else {
                        result[i][j] = result[i][j];
                    }
                }
            }
        }
    }
    else {
        //left
        bool moved = true;
        while(moved==true) {
            moved = false;
            for(int i=0; i<n; i++) {
                for(int j=1; j<n; j++) {
                    if(result[i][j] != 0 && result[i][j-1] == 0) {
                        result[i][j-1] = result[i][j];
                        combined[i][j-1] = combined[i][j];
                        combined[i][j] = 0;
                        result[i][j] = 0;
                        moved = true;
                    }
                    else if(result[i][j] != 0 && combined[i][j] == 0 && result[i][j-1] == result[i][j] && combined[i][j-1] == 0) {
                        result[i][j-1] = 2*result[i][j];
                        result[i][j] = 0;
                        combined[i][j-1] = 1;
                        moved = true;
                    }
                    else {
                        result[i][j] = result[i][j];
                    }
                }
            }
        }
    }

    return result;
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int** first;
    
    first = new int*[n];
    for(int i=0; i<n; i++) {
        first[i] = new int[n];
        for(int j=0; j<n; j++) {
            cin >> first[i][j];
        }
    }

    queue<pair<int**, int> > queue;
    queue.push(pair<int**, int>(first, 0));
    int max = -1;
    while(!queue.empty()) {
        pair<int**, int> now = queue.front();
        queue.pop();

        if(now.second == 5) {
            int now_max = find_max(now.first, n);
            if(now_max > max) {
                max = now_max;
            }
            continue;
        }

        for(int i=0; i<4; i++) {
            int** moved = move(now.first, n, i);
            queue.push(pair<int**, int>(moved, now.second + 1));
        }
    }
    cout << max << "\n";
	return 0;
}