[백준 12094번] 2048 (Hard)

문제 링크: https://www.acmicpc.net/problem/12094

12094번: 2048 (Hard)

<문제 풀이> 백트랙킹

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

12100번: 2048 (Easy)

2048 Easy 문제에서 백트랙킹이 추가된 문제이다.

 

1. 이동 후 항상 변화가 있어야 한다. (이동 후 배열의 값이 바뀌었는지 체크)

2 4 8

2 4 8 

2 4 8

에서 left를 하면

2 4 8

2 4 8

2 4 8

변화가 없는 상태에서 계속 연산을 해봤자 의미가 없다. 

-> 최대 k 번까지 이동했을 때 최댓값을 구하고 싶은 거니깐 항상 변화가 있어야 한다.

 

2. k번 이동했을 때 현재 배열의 값으로 10번까지 이동해서 만들 수 있는 최댓값이 지금 까지 갱신한 최댓값 이하이면  더 이상 진행하지 않는다.

1번 이동했을 때 현재 배열의 값의 최대값이 2라면

10번 이동했을 때 현재 배열의 최댓값으로 만들 수 있는 수는 2048이다.

2 * 2 ^ (10 - 1) = 1024  -> ( 현재 배열의 값의 최대값 * 2^(10 - k) ) 

그런데 지금까지 갱신한 최댓값이 4096이라면

아무리 최고의 상황이 나오더라도 10번까지 이동해서 4096을 만들 수 없다

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
int N;
int board[20][20];
bool visited[20][20];
int res = 0;
int max_res = 0;
void printBoard() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << "\n\n";
}
 
void rotate() {
    int temp[20][20];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = temp[N - j - 1][i];
        }
    }
}
 
 
void left() {
    for (int i = 0; i < N; i++) {
        int moved[20] = { 0, };
        bool combined[20] = { 0, };
        int idx = 0;
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0) continue;
            if (moved[idx] == 0) {
                moved[idx] = board[i][j];
            }
            else if (moved[idx] && combined[idx]) {
                moved[++idx] = board[i][j];
            }
            else if (moved[idx] == board[i][j]){
                moved[idx] *= 2;
                combined[idx++] = true;
           
            }
            else {
                moved[++idx] = board[i][j];
            }
 
            
        }
        for (int j = 0; j < N; j++) {
            board[i][j] = moved[j];
        }
    }
}
 
void up() {
    rotate();
    rotate();
    rotate();
    left();
    rotate();
}
void right() {
    rotate();
    rotate();
    left();
    rotate();
    rotate();
 
}
 
void down() {
    rotate();
    left();
    rotate();
    rotate();
    rotate();
}
 
void tempToBoard(int temp[][20]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = temp[i][j];
        }
    }
}
 
bool isChanged(int arr1[][20], int arr2[][20]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr1[i][j] != arr2[i][j]) return true;
        }
    }
    return false;
}
 
void dfs(int k) {
    int temp[20][20];
    int cur_max = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[i][j];
            if (board[i][j] >= cur_max) cur_max = board[i][j];
        }
    }
    res = max(res, cur_max);
 
    if (k == 10) return;
    if (cur_max * 1 << (10 - k) <= res) return;
 
    left();
    if (isChanged(temp, board)) {
        dfs(k + 1);
        tempToBoard(temp);
    }
    right();
    if (isChanged(temp, board)) {
        dfs(k + 1);
        tempToBoard(temp);
    }
    up();
    if (isChanged(temp, board)) {
        dfs(k + 1);
        tempToBoard(temp);
    }
    down();
    if (isChanged(temp, board)) {
        dfs(k + 1);
        tempToBoard(temp);
    }
 
 
 
 
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
            if (board[i][j] >= max_res) max_res = board[i][j];
        }
    }
    
    dfs(0);
    cout << res;
   
    return 0;
}