[BOJ] 12094. 2048(Hard)

*2048(easy)와 풀이단계는 비슷하지만, 가지치기를 해줘야 한다. (최대 횟수가 2배로 늘었기 때문에)

-가지치기

1) 변경된 맵이 변경되기 이전의 맵과 동일한 경우 -> 이 방향으로는 더 이상 나아가지 않는다. 

2) 맵에서 최대값을 찾을때, 최대값은 2승씩 커진다. (cnt==10 이라면 가장 최대값은 1024가 될 것이다. )

이 특징을 이용해서 현재 depth에서 최대값에 도달할 수 있는 지 확인한다.

(즉, 한 번 10번까지 변경된 맵에서 최대값을 추출한 후 maxBlock[10] = 1024 / maxBlock[9] = 512 .... 이런 식으로 미리 저장을 해 놓는다.)

*실제 최대값은 1024가 아닐 수 있다. 

3) 현재 맵에서 구한 최대값이 현재 depth(==cnt)에서 나와야 하는 최대값보다 작은 경우에는 더 이상 보지 않는다. 

 

*가지치기 1번 때문에 맵을 먼저 변경한 후에 dfs를 돌리도록 변경했다. 

쉬운 버전 참고

2019/08/01 - [BOJ/C++] - [BOJ] 12100. 2048(easy)

[BOJ] 12100. 2048(easy)

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

#include <iostream> #include <vector> #include <cstring> #include <algorithm> /* BOJ 12094. 2048 hard https://www.acmicpc.net/problem/12094 */   using namespace std;   int n, ans = 0; int maxBlock[11];   int map[21][21] = { {0} };   //void print(int(*map)[21]) { // //  cout << '\n'; //  for (int i = 0; i < n; i++) { //      for (int j = 0; j < n; j++) { //          cout << map[i][j] << ' '; //      } //      cout << '\n'; //  } //  cout << '\n'; //} bool check(int(*chk)[21]) {     //이전의 것과 같은 지 확인한다.     for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {             if (chk[i][j] != map[i][j]) return false;         }     }     return true; } void moveBlocks(int dir) {     //방향에 따라서 이동     //다음 호출 함수로 넘길 맵     int c_map[21][21] = { {0} };       vector<int> combine, list;       int tmp = 0;     for (int i = 0; i < n; i++) {         list.clear();         combine.clear(); //현재 행에 저장될 숫자들을 저장           for (int j = 0; j < n; j++) {             if (dir <= 1) {                 //북 남                 if (map[j][i]) list.push_back(map[j][i]);             }             else {                 if (map[i][j]) list.push_back(map[i][j]);             }         }         //동, 남의 경우에는 리버스한다.         if (dir == 1 || dir == 3) {             reverse(list.begin(), list.end());         }           for (int j = 0; j < list.size(); j++) {             if (j != list.size() - 1 && list[j] == list[j + 1]) {                 combine.push_back(list[j] * 2);                 j++;             }             else combine.push_back(list[j]);         }         //이제 순서대로 넣는다.           //방향에 맞게 c_map에 넣는다.         for (int j = 0; j < combine.size(); j++) {             if (dir == 0) {                 //북->위에서부터 채운다.                 c_map[j][i] = combine[j];             }             else if (dir == 1) {                 c_map[n - j - 1][i] = combine[j];             }             else if (dir == 2) {                 //서                 c_map[i][j] = combine[j];             }             else if (dir == 3) {                 c_map[i][n - j - 1] = combine[j];             }           }     }     memcpy(map, c_map, sizeof(map)); } void dfs(int cnt) {       int max = 0;     for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {             max = max > map[i][j] ? max : map[i][j];         }     }     if (max <= maxBlock[cnt]) return; //합쳐도 더 커질 가능성이 없는 depth       if (cnt == 10) {         ans = ans > max ? ans : max;           int tmp = ans;         while (cnt > 0) {             maxBlock[cnt--] = tmp;             tmp /= 2;         }         return;     }       int c_map[21][21];     memcpy(c_map, map, sizeof(map));       for (int k = 0; k < 4; k++) {                   moveBlocks(k);         if (check(c_map)) continue;         dfs(cnt + 1);         memcpy(map, c_map, sizeof(map));     } } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n;       int max = 0;     for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {             cin >> map[i][j];             ans = ans > map[i][j] ? ans : map[i][j];         }     }       dfs(0);       cout << ans << '\n';     return 0; }