[G1] 백준 12100번 2048 (Easy) C++ 백트래킹, 구현, 시뮬레이션, 브루트포스 알고리즘

리뷰

 

2048게임을 구현하는 문제, 시뮬레이션만 잘 작성하면 쉽게 풀 수 있으나 문제를 잘 읽어보아야 할듯 하다.

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

 

문제 풀이

전역 변수

• n : 맵의 행, 열을 저장할 변수
• ans : 최대값을 저장하기 위한 변수
• map : 맵 정보를 입력받을 2차원 정수형 벡터

 

1. n값을 입력 받고 map을 n * n크기로 초기화 해준 뒤 맵의 정보을 입력 받아준다.
2. dfs를 통해 상하좌우로 미는 작업을 완전 탐색으로 구현해 준다, 매개변수는 시도한 횟수 level과 맵을 참조한다.
3. 기저 조건으로 level이 5에 도달하면 5번 작업을 한 상태이므로 맵을 체크하여 최대 값을 갱신해 준다.
4. 4방향으로 탐색을 하며 상하좌우로 맵을 미는 작업을 한 후에 재귀를 실행해 준다.
5. 이때 맵은 매개변수로 받은 map을 복사하여 시뮬레이션 작업 후 재귀로 넘겨주는 작업이 필요하다.
6. 시뮬레이션 함수의 매개 변수로는 복사한 map과 방향 정보인 dir를 넘겨받는다.
7. dir이 0, 1, 2, 3일 경우 각각 오른쪽, 왼쪽, 아래, 위 방향으로 숫자들을 밀어줄 것이다.
8. 오른쪽으로 이동할 경우 맵의 오른쪽부터 숫자들을 큐에 담고 다시 맵의 오른쪽부터 숫자를 배치해 준다.
9. 이때 큐에서 값을 하나 뽑아내고, 다음 큐의 맨 앞의 수가 동일하다면 뽑아낸 값을 2배 해주고 큐의 앞 수를 버려준다.
10. 만약 동일하지 않거나 큐에 더이상 값이 없을 경우 숫자를 놔준 후 좌표값을 왼쪽으로 이동해 주면 된다.
11. 이 작업을 상하좌우 모든 경우에 대해 지정해 준다, 시뮬레이션 작업은 이게 끝이다.
12. 기저조건에서 찾은 최대값을 출력해 주면 된다.

 

참고 사항

1. 시도해 보진 않았지만 아이디어로 시뮬레이션 작업을 할때 ans값을 갱신해 주던가, int형으로 return 해주어서 dfs의 매개변수로 활용해도 좋을 것 같다.
2. 위 내용을 잘 활용한다면 level당 *2가 되는 형식이니 가지치기를 잘 수행할 수 있을 것이다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n, ans = 0;
vector<vector<int>> map;

void simulation(vector<vector<int>>& lst, int dir) {
    if (dir == 0) { // 오른쪽으로 이동
        for (int i = 0; i < n; i++) {
            queue<int> q;
            for (int j = n - 1; j >= 0; j--) if (lst[i][j]) q.push(lst[i][j]);

            // 초기화
            fill(lst[i].begin(), lst[i].end(), 0);

            int index = n - 1;
            while (!q.empty()) {
                int value = q.front(); q.pop();
                if (!q.empty() && value == q.front()) { // 합치기
                    lst[i][index--] = value * 2;
                    q.pop(); // 두 개의 블록을 하나로 합친 후 pop
                }
                else {
                    lst[i][index--] = value;
                }
            }
        }
    }
    else if (dir == 1) { // 왼쪽으로 이동
        for (int i = 0; i < n; i++) {
            queue<int> q;
            for (int j = 0; j < n; j++) if (lst[i][j]) q.push(lst[i][j]);

            fill(lst[i].begin(), lst[i].end(), 0);

            int index = 0;
            while (!q.empty()) {
                int value = q.front(); q.pop();
                if (!q.empty() && value == q.front()) {
                    lst[i][index++] = value * 2;
                    q.pop();
                }
                else {
                    lst[i][index++] = value;
                }
            }
        }
    }
    else if (dir == 2) { // 아래로 이동
        for (int j = 0; j < n; j++) {
            queue<int> q;
            for (int i = n - 1; i >= 0; i--) if (lst[i][j]) q.push(lst[i][j]);

            for (int i = n - 1; i >= 0; i--) lst[i][j] = 0;

            int index = n - 1;
            while (!q.empty()) {
                int value = q.front(); q.pop();
                if (!q.empty() && value == q.front()) {
                    lst[index--][j] = value * 2;
                    q.pop();
                }
                else {
                    lst[index--][j] = value;
                }
            }
        }
    }
    else if (dir == 3) { // 위로 이동
        for (int j = 0; j < n; j++) {
            queue<int> q;
            for (int i = 0; i < n; i++) if (lst[i][j]) q.push(lst[i][j]);

            for (int i = 0; i < n; i++) lst[i][j] = 0;

            int index = 0;
            while (!q.empty()) {
                int value = q.front(); q.pop();
                if (!q.empty() && value == q.front()) {
                    lst[index++][j] = value * 2;
                    q.pop();
                }
                else {
                    lst[index++][j] = value;
                }
            }
        }
    }
}


void dfs(int level, vector<vector<int>>& map) {
    if (level == 5) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = max(ans, map[i][j]);
            }
        }
        return;
    }
    for (int i = 0; i < 4; i++) {
        vector<vector<int>> lst = map;
        simulation(lst, i);
        dfs(level + 1, lst);
    }
}

int main() {
    cin >> n;
    map.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }

    dfs(0, map);
    cout << ans;
}