Boj 12094) 2048(hard)

문제

백준 12094

설명

DFS 구현

쉬운 방법은 움직이는 방향에 따른 줄마다

• 간단한 배열이나 리스트를 만들어서
• 유효숫자만 뽑아내서 계산한 후에
• 결과를 끝부분에 집어넣고 나머지를 0으로 넣으면 됨.
• 여러번 루프를 돌아야해서 느리지만 실수를 확실히 덜함.
  • 난 800ms 가까이 나왔음

다른 방법은 움직이는 방향에 따른 줄마다

• 비교할 포인터 p1, p2 랑 끝부분에 차례로 넣은 포인터 updated 를 두어서 루프 돌면서 한번에 처리하는 것임
• p2 는 0 이 아닌 수를 먼저 찾으러 가고
• p1 은 p2 앞의 0 이 아닌 수를 가리키게 해서
• 둘을 비교한 후 같은지에 따라 board[updated] 에 적절한 값을 줌
• 그리고 updated 는 다음 값을 가르키게 함.
• updated 되지 않은 값들은 다 0을 줌.

Pruning

다음 두가지 경우에서 Pruning 안하면 시간초과남

1. 움직여도 똑같은 경우
2. 움직여도 최댓값을 못넘는 경우
   • 나는 여기서 등호 빼먹었는데 이걸로 시간초과가 났음.

시간 복잡도

O(\(2^N \times N^2\))

코드

int MAX_TIME = 10;
int n, nn;
int board[21 * 21];
int ans = 0;

enum DIR { L, R, U, D };
void Do(DIR dir)
{
	int pivot, p_offset, l_offset;

	switch (dir)
	{
	case L: pivot = 0;           p_offset = n; l_offset = 1;  break;
	case R: pivot = n - 1;       p_offset = n; l_offset = -1; break;
	case U: pivot = 0;           p_offset = 1; l_offset = n; break;
	case D: pivot = n * (n - 1); p_offset = 1; l_offset = -n; break;
	}
	
	for (int i = 0; i < n; i++, pivot += p_offset)
	{
		int p1 = pivot, p2 = p1, updated = p1;
		while(p2 != pivot + l_offset * (n-1))
		{
			p2 += l_offset;
			if (board[p2] == 0) continue;
			while(board[p1] == 0) p1 += l_offset;
			if (p1 != p2)
			{
				if (board[p1] == board[p2])
				{
					board[updated] = board[p2] + board[p2];
					board[p2] = 0;
				}
				else board[updated] = board[p1];
				
				updated += l_offset;
				p1 = p2;
			}
	
		}
		swap(board[updated], board[p1]); // p2 is out of bound, p1 is end of line.
		updated += l_offset;
	
		while (updated != pivot + l_offset * n)
		{
			board[updated] = 0;
			updated += l_offset;
		}
	}
}

bool CheckPrune(int* backup, int cur_max, int cur)
{
	if ((cur_max << (MAX_TIME - cur - 1)) <= ans)
		return true;

	for (int i = 0; i < nn; i++)
		if (backup[i] != board[i])
			return false;
	
	return true;
}

void DFS(int cur)
{
	if (cur == MAX_TIME) {
		ans = max(ans, *max_element(board, board + nn));
		return;
	}

	int backup[21 * 21];
	copy(board, board + nn, backup);
	
	for(int i = 0 ; i < 4; i++)
	{
		Do((DIR)i);
	
		int cur_max = *max_element(board, board + nn);
	
		if (CheckPrune(backup, cur_max, cur)) {
			ans = max(ans, cur_max);
			copy(backup, backup + nn, board);
			continue;
		}
	
		DFS(cur + 1);
		copy(backup, backup + nn, board);
	}

}


int main()
{
	cin >> n; nn = n * n;

	for (int i = 0; i < nn; i++)
		cin >> board[i];
	
	DFS(0);
	cout << ans;
}