[BOJ/12100/C++] 2048(Easy)

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

문제

• 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
  이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다.
• 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
• 실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

조건

• 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
• 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

풀이

유명한 게임인 2048을 구현하는 문제이다. 여기서 구현해야할 것은 2가지이다.

1. 배열을 상,하,좌,우로 기울여본다.

2. 5번 동안 움직일 수 있는 모든 경우의 수에 대해서 확인한다.

   2번 경우는, 현재 움직일 수 있는 경우가 (상,하,좌,우) 4가지 경우의 수로 5번 움직이니까 4^5, 즉 1024가지 경우의 수가 나올 수 있다. 4진법 수라고 생각하고 00000 ~ 33333 까지 확인하면 된다.

결국 이 문제는 , 배열을 상,하,좌,우로 기울여본다라는 개념을 구현하는 문제이다. 배열을 기울여본다는걸 그림으로 표현하면, 아래와 같아진다. 여기서 4가 8이되는건 문제의 조건 때문이다.

배열 기울이기

배열을 왼쪽으로 기울이는걸 구현해본다고 생각해보자. 우선적으로 복잡하게 생각하지말고 , 문제에 조건도 생각하지말아보자.

• 4->8이 되는 등은 if문을 추가하면 될 일이다. 그리고, 각 행에 대해서 적용해주면 되기 때문에, 1차원 배열을 움직일 수 있으면 다 움직일 수 있다.

가장 먼저 떠오르는 방법은 , 새로운 배열을 하나 만들어서 원소가 있으면 앞에서 부터 차례대로 채워주면 될 것 같다. 그러기 위해선, 현재 자신의 위치를 기억하고 있는 cursor가 한 개가 필요하다.

코드로 단순히 작성한다면 아래와 같이 될 거 같다.

int arr = [0,4,0,4,8,9] 
int tmp[6] ={};
int idx =0;
for(int i=0;i<6;i++){
	if(arr[i]==0) continue;
    if(tmp[idx]==0)
    	tmp[idx] = arr[i];
    else{
    	tmp[++idx] = arr[i];
    }
}

충돌이 났을 때, 즉 위에서는 4와 4가 만났을 때 처리를 어떻게 해줄 수 있을까 ?
cursor와 arr[i]가 같다면 -> 현재 위치 값 x2 커서를 다음으로 옮김(한번 연산한 건 더 연산이 불가능)

int arr = [0,4,0,4,8,9] 
int tmp[6] ={};
int idx =0;
for(int i=0;i<6;i++){
	if(arr[i]==0) continue;
    if(tmp[idx]==0)
    	tmp[idx] = arr[i];
    else if(tmp[idx] ==arr[i]){
    	tmp[idx] *=2;
    }
    else{
    	tmp[++idx] = arr[i];
    }
}

위와 같은 규칙으로 오른쪽, 위쪽, 아래쪽도 좌표만 신경써서 바꾸어 주면된다.
오른쪽으로 기울일 때는 배열의 맨 끝부터 시작해서, 탐색을 해야하고, 위쪽으로 갈 때는 배열의 제일 위 부터 column을 반복해야한다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N;

int board_A[21][21];
int board_B[21][21];

void move_down()
{
  for (int x = 0; x < N; x++)
  {
    int tmp[21] = {};
    int idx = N - 1;
    for (int y = N - 1; y >= 0; y--)
    {
      if (board_B[y][x] == 0)
        continue;
      if (tmp[idx] == 0)
        tmp[idx] = board_B[y][x];
      else if (tmp[idx] == board_B[y][x])
        tmp[idx--] *= 2;
      else
        tmp[--idx] = board_B[y][x];
    }
    for (int i = 0; i < N; i++)
    {
      board_B[i][x] = tmp[i];
    }
  }
}

void move_right()
{
  for (int i = 0; i < N; i++)
  {
    int tmp[21] = {};
    int idx = N - 1;
    for (int j = N - 1; j >= 0; j--)
    {
      if (board_B[i][j] == 0)
        continue;
      if (tmp[idx] == 0)
        tmp[idx] = board_B[i][j];
      // 비어있지 않을 때,
      else if (tmp[idx] == board_B[i][j])
        tmp[idx--] *= 2;
      else
        tmp[--idx] = board_B[i][j];
    }
    for (int j = 0; j < N; j++)
    {
      board_B[i][j] = tmp[j];
    }
  }
}

void move_up()
{
  for (int x = 0; x < N; x++)
  {
    int tmp[21] = {};
    int idx = 0;
    for (int y = 0; y < N; y++)
    {
      if (board_B[y][x] == 0)
        continue;
      if (tmp[idx] == 0)
        tmp[idx] = board_B[y][x];
      else if (tmp[idx] == board_B[y][x])
        tmp[idx++] *= 2;
      else
        tmp[++idx] = board_B[y][x];
    }
    // 결과반영
    for (int i = 0; i < N; i++)
    {
      board_B[i][x] = tmp[i];
    }
  }
}

void move_left()
{

  for (int i = 0; i < N; i++)
  {
    int tmp[21] = {};
    int idx = 0;
    // 포인터 한 개와 배열 1개를 만들어준다.
    for (int j = 0; j < N; j++)
    {
      if (board_B[i][j] == 0)
        continue;
      if (tmp[idx] == 0)
        tmp[idx] = board_B[i][j];
      else if (tmp[idx] == board_B[i][j])
        tmp[idx++] *= 2;
      else
        tmp[++idx] = board_B[i][j];
    }
    // 결과반영
    for (int j = 0; j < N; j++)
    {
      board_B[i][j] = tmp[j];
    }
  }
}

void copy_board()
{
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      board_B[i][j] = board_A[i][j];
}
int main()
{
  fastio;
  cin >> N;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      cin >> board_A[i][j];

  int mx = 0;
  // 5번동안 상,하,좌,우 기울일 경우의 수 모두 해보기
  for (int tmp = 0; tmp < 1024; tmp++)
  {
    // 원상복구 시키기
    copy_board();
    int brute = tmp;
    for (int i = 0; i < 5; i++)
    {
      // 위 , 오른쪽, 아래, 왼쪽 순
      int dir = brute % 4;
      brute /= 4;
      if (dir == 0)
        move_up();
      else if (dir == 1)
        move_right();
      else if (dir == 2)
        move_down();
      else
        move_left();
    }
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        mx = max(mx, board_B[i][j]);
  }
  cout << mx << '\n';
  return 0;
}