매일 C++ day 15 / 2048 (Easy)

2021-06-12

2048 (Easy)

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

동서남북 모든 방향으로 움직이는 함수를 각각 만들다 보니 코드가 너무 길어져 만든 나도 알아볼 수 없었다.

그래서 숏코딩 코드를 보고 주석을 달아봤다.

입력

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

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

int main() {
	cin >> n;
	int arr[20][20];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	dfs(0, arr);
	cout << maxv;
}

dfs

깊이 우선 탐색의 매개변수로 depth와 보드판 arr을 받는다.

기존에 내가 만든 코드는 4방향 각각 함수를 만든 반면

여기서는 한 방향으로만 움직이는 대신 보드판을 회전시킨다.

int temp[20][20];
for (int i = 0; i < n; i++) 
{
  for (int j = 0; j < n; j++) 
  {
    temp[i][j] = arr[n - j - 1][i];
  }
}
memcpy(arr, temp, sizeof(temp));

왼쪽 이동

새로운 보드판 brr을 0으로 초기화한다.

cur은 다음 brr 블록을 가르키고 ok는 블록을 하나로 합칠 수 있는지의 여부를 알려준다.

cur과 ok가 있으면 코드를 매우 많이 단축시킬 수 있다!

ok가 1이고 brr[i][cur - 1] == arr[i][j] 이면, brr[i][cur - 1]의 값을 두배로 증가시키고 ok를 0으로 바꾸지만 cur은 증가하지 않는다.

ok가 0이라면 brr[i][cur]에 arr[i][j]을 넣고 cur을 1 증가시킨다.

for (int i = 0; i < n; i++) {
  int cur = 0, ok = 0;
  for (int j = 0; j < n; j++) {
    if (arr[i][j]) {
      if (ok && brr[i][cur - 1] == arr[i][j]) {
        brr[i][cur - 1] <<= 1;
        ok = 0;
      }
      else {
        brr[i][cur++] = arr[i][j];
        ok = 1;
      }
    }
  }
}

void dfs(int depth, int arr[20][20]) 
{	
	if (depth >= 5) 
  {
		for (int i = 0; i < n; i++) 
    {
			for (int j = 0; j < n; j++) 
      {
				if (arr[i][j] && arr[i][j] > maxv) 
        {
					maxv = arr[i][j];
				}
			}
		}
		return;
	}
  
  // 깊이 5까지 탐색하고 최대값을 반환한다.
  

	for (int i = 0; i < 4; i++) 
  {
		int brr[20][20];
		memset(brr, 0, sizeof(brr));
    // 보드를 0으로 초기화

		for (int i = 0; i < n; i++) 
    {
			int cur = 0, ok = 0;
			for (int j = 0; j < n; j++) 
      {
				if (arr[i][j]) 
        { 
					if (ok && brr[i][cur - 1] == arr[i][j]) 
          {
						brr[i][cur - 1] <<= 1; 
						ok = 0;
					}
					else 
          {
						brr[i][cur++] = arr[i][j];
						ok = 1;
					}
				}
			}
		}

		dfs(depth + 1, brr);
  
  
    // !!!!보드판을 오른쪽 90도 회전!!!!
		int temp[20][20];
		for (int i = 0; i < n; i++) 
    {
			for (int j = 0; j < n; j++) 
      {
				temp[i][j] = arr[n - j - 1][i];
			}
		}
		memcpy(arr, temp, sizeof(temp));
	}
}