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

리뷰

 

2048(Easy)의 어려운 버전, 재귀의 깊이가 기존 5에서 10으로 늘어났다.

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

 

가지치기를 최소 두개를 추가해 줘야 시간 초과를 막을 수 있는 문제인 듯

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

 

전역 변수

• n, ans : 맵의 행과 열의 길이를 저장할 정수형 변수 n, 최대값을 저장할 변수 ans
• map : 초기 맵의 정보를 담을 2차원 정수 벡터

 

함수

1. simulation

int simulation(vector<vector<int>>& lst, vector<vector<int>>& temp, int dir, int val)

 

 

상하좌우로 이동하여 인접한 같은 수를 합치고 벽으로 숫자를 미는 작업을 진행할 시뮬레이션 함수

1. 시뮬레이션 전, 후의 맵 정보 lst, temp와 작업을 수행할 방향 dir, 현재까지의 최대값 val을 매개변수로 받아준다.
2. 각 방향에 따라 맵 lst의 행, 열을 참조하여 모든 수를 정수형 배열 q에 담아준다.
3. 배열에 저장된 수를 선입된 순으로 체크해 주며 만약 인접한 두 수가 동일하다면 두 수를 합쳐준다.
4. 인접하지 않다면 temp의 시뮬레이션 반대 방향의 끝부터 숫자를 배치해 주면 된다.
5. 만약 두 수가 동일하여 합쳐준 경우 인접한 수는 소멸되었으므로 인덱스를 다음으로 이동해 주어야 한다.
6. 이때 현재까지의 최대값 val과 비교하여 val보다 크다면 val을 갱신해 주어야 한다.
7. 시뮬레이션이 완료된 후에 val을 return 해준다.

2. dfs

void dfs(int level, vector<vector<int>>& map, int val)

 

1. 각 재귀 단계에서 최대값을 찾을 때 까지 최대 10번 재귀를 수행하는 함수
2. 재귀 단계를 나타낼 level과 현재 맵 정보 map, 현재 재귀 단계에서의 최대값 val을 매개변수로 갖는다.
3. 4방향을 탐색하여 각각 상하좌우로 숫자를 밀고 합치는 시뮬레이션 작업을 수행한다.
4. 만약 시뮬레이션 전과 후가 동일하다면 해당 케이스는 더이상 탐색할 필요가 없다.
5. 시뮬레이션 후 맵 정보가 달라졌다면 재귀 단계를 높히고 시뮬레이션한 맵과 리턴받은 val로 재귀를 실행한다.
6. (가지치기 1) 만약 재귀 단계가 10에 도달했을 경우 ans에 val값을 최신화 해주고 리턴 해준다.
7. (가지치기 2) 만약 현재 단계에서 매번 값을 합쳤다고 가정했을때 ans보다 작거나 같으면 더이상 탐색할 필요가 없다.

 

문제풀이

1. n값을 입력 받고, map 정보를 n * n으로 초기화 및 값을 입력 받아준다. 이때 맵의 max값을 ans로 저장한다.
2. 재귀단계 0, 초기 맵 정보 map, 초기 최대값 정보 ans를 매개변수로 전달하여 dfs함수를 실행한다.
3. 각 방향으로의 시뮬레이션을 진행하고, 기저조건에 해당하지 않는다면 재귀를 추가로 수행한다.
4. ans에 저장된 최대값을 출력해 준다.

 

참고 사항

dfs함수의 가지치기 1, 2에 해당하는 가지치기를 통해 통과하였다, 둘 중 하나라도 수행하지 않으면 시간초과가 났다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

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

int simulation(vector<vector<int>>& lst, vector<vector<int>>& temp, int dir, int val) {
    if (dir == 0) { // 오른쪽으로 이동
        for (int i = 0; i < n; i++) {
            int q[20], qidx = 0, qcnt = 0;
            for (int j = n - 1; j >= 0; j--) if (lst[i][j]) q[qcnt++] = lst[i][j];

            int index = n - 1;
            while (qidx < qcnt) {
                int value = q[qidx];
                if (qidx + 1 < qcnt && value == q[qidx + 1]) { // 합치기
                    temp[i][index--] = value * 2;
                    val = max(val, value * 2);
                    qidx++;
                }
                else temp[i][index--] = value;
                qidx++;
            }
        }
    }
    else if (dir == 1) { // 왼쪽으로 이동
        for (int i = 0; i < n; i++) {
            int q[20], qidx = 0, qcnt = 0;
            for (int j = 0; j < n; j++) if (lst[i][j]) q[qcnt++] = lst[i][j];

            int index = 0;
            while (qidx < qcnt) {
                int value = q[qidx];
                if (qidx + 1 < qcnt && value == q[qidx + 1]) { // 합치기
                    temp[i][index++] = value * 2;
                    val = max(val, value * 2);
                    qidx++;
                }
                else temp[i][index++] = value;
                qidx++;
            }
        }
    }
    else if (dir == 2) { // 아래로 이동
        for (int j = 0; j < n; j++) {
            int q[20], qidx = 0, qcnt = 0;
            for (int i = n - 1; i >= 0; i--) if (lst[i][j]) q[qcnt++] = lst[i][j];

            int index = n - 1;
            while (qidx < qcnt) {
                int value = q[qidx];
                if (qidx + 1 < qcnt && value == q[qidx + 1]) { // 합치기
                    temp[index--][j] = value * 2;
                    val = max(val, value * 2);
                    qidx++;
                }
                else temp[index--][j] = value;
                qidx++;
            }
        }
    }
    else if (dir == 3) { // 위로 이동
        for (int j = 0; j < n; j++) {
            int q[20], qidx = 0, qcnt = 0;
            for (int i = 0; i < n; i++) if (lst[i][j]) q[qcnt++] = lst[i][j];

            int index = 0;
            while (qidx < qcnt) {
                int value = q[qidx];
                if (qidx + 1 < qcnt && value == q[qidx + 1]) { // 합치기
                    temp[index++][j] = value * 2;
                    val = max(val, value * 2);
                    qidx++;
                }
                else temp[index++][j] = value;
                qidx++;
            }
        }
    }
    return val;
}


void dfs(int level, vector<vector<int>>& map, int val) {
    if (level == 10) {
        ans = max(ans, val);
        return;
    }
    if (val * pow(2, 10 - level) <= ans) return;
    for (int i = 0; i < 4; i++) {
        vector<vector<int>> temp(n, vector<int>(n, 0));
        int new_val = simulation(map, temp, i, val);
        int flag = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != temp[i][j]) {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag) dfs(level + 1, temp, new_val);
    }
}

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];
            ans = max(ans, map[i][j]);
        }
    }

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