[C++] 백준 12100번 2048(Easy)

문제

백준 12100번 2048(Easy)

풀이

블럭을 전부 왼쪽으로 미는 경우만 만든후 90도씩 회전시키며 4가지 방향으로 이동할 수 있게했다. 블럭을 이동시키는 것이 구현하기 까다로웠는데 나는 먼저 숫자가 같은 블럭들을 합친후 해당방향으로 미는 방식으로 구현했다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n;
int ans=0;
int board[20][20];

// 회전
void rotate(int (*arr)[20]){
  int tmp[20][20];

  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++) 
      tmp[j][n-1-i] = arr[i][j];

  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++) 
      arr[i][j] = tmp[i][j];
}

// 왼쪽으로 밀기
void push(int (*arr)[20]){
  
  for (int i=0; i<n; i++){
    int idx = 0;

    for (int j=0; j<n; j++){
      while (arr[i][idx] == 0) idx++;
      if (arr[i][j] == 0) continue;
      if (idx == j) continue;
      
      // 합치기
      if (arr[i][j] == arr[i][idx]){
        arr[i][idx] *= 2;
        arr[i][j] = 0;
        idx++;
      }
      else idx++;
    }
    // 밀기
    idx = 0;
    for (int j=0; j<n; j++){
      if (arr[i][j] == 0) continue;

      if (idx == j) idx++;
      else{
        arr[i][idx] = arr[i][j];
        arr[i][j] = 0;
        idx++;
      }
    }
  }
}

int getMax(int (*arr)[20]){
  int ret = 0;
  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      ret = max(ret, arr[i][j]);
  return ret;
}

void solve(int depth, int (*arr)[20]){
  int tmp[20][20];

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

  if (depth != 0) push(tmp);

  if (depth == 5){
    ans = max(ans, getMax(tmp));
    return;
  }

  solve(depth+1, tmp);

  for (int i=0; i<3; i++){
    rotate(tmp);
    solve(depth+1, tmp);
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      cin >> board[i][j];

  solve(0,board);

  cout << ans;
}