[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)

 

 

#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; }