BOJ 12094 | 2048 (Hard)

솔직히 당황했다. 어디서 최적화를 해야 할 지 처음에 감이 안 잡혀서 고생했는데, 질문 게시판을 좀 보고 깨달았다.

1. Move 후 변화가 없다면 이후 탐색은 무의미하다.
2. maxvalue를 업데이트하면서 현재 깊이에서 도달 가능한 범위인지 체크한다.

2번이 핵심인데, 이 문제는 움직임에 10회 제한이 있기 때문에 N을 달성 가능한 방법을 찾은 상태에서 현재 노드에서 최댓값이 $N / 2^{10-depth}$ 이하라면 앞으로 모든 경로에서 최댓값이 merge 된다고 하더라도 마지막에 $N$ 이하를 달성하기 때문에 바로 끝내도 된다.

이러고도 TLE가 났었는데, 솔직히 여기서 살짝 막막했다. 아무리 생각해도 더 줄일 방법이 없는데 1% 시간초과 먹으니 프로그램 구조 문제인가 싶었다.

다른 사람들이 작성한 코드를 보니까 2차원 배열을 복사할 때 memcpy를 쓰는 걸 보고 나도 반복문을 memcpy로 대체해 보니 AC가 났다.

앞으로 배열 복사에는 memcpy를 이용하도록 하자.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int N;
int maxvalue = 0;

int xd[4] = {-1, 0, 1, 0};
int yd[4] = {0, 1, 0, -1};

int board[21][21];

void leftmove(){
	const int dir = 3;
	int merge[21][21] = {0, };
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			if (board[i][j] == 0) continue;
			
			int x = i, y = j;
			while (true){
				if (x + xd[dir] < 1 || x + xd[dir] > N) break;
				if (y + yd[dir] < 1 || y + yd[dir] > N) break;
				
				int &next = board[x+xd[dir]][y+yd[dir]];
				
				if (next == 0){
					next = board[x][y];
					board[x][y] = 0;
				}
				else if (next == board[x][y] && !merge[x+xd[dir]][y+yd[dir]] && !merge[x][y]){ // merge
					board[x][y] = 0;
					next *= 2;
					merge[x+xd[dir]][y+yd[dir]] = 1;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void upmove(){
	const int dir = 0;
	int merge[21][21] = {0, };
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			if (board[i][j] == 0) continue;
			
			int x = i, y = j;
			while (true){
				if (x + xd[dir] < 1 || x + xd[dir] > N) break;
				if (y + yd[dir] < 1 || y + yd[dir] > N) break;
				
				int &next = board[x+xd[dir]][y+yd[dir]];
				
				if (next == 0){
					next = board[x][y];
					board[x][y] = 0;
				}
				else if (next == board[x][y] && !merge[x+xd[dir]][y+yd[dir]] && !merge[x][y]){ // merge
					board[x][y] = 0;
					next *= 2;
					merge[x+xd[dir]][y+yd[dir]] = 1;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void downmove(){
	const int dir = 2;
	int merge[21][21] = {0, };
	for (int i = N; i >= 1; i--){
		for (int j = N; j >= 1; j--){
			if (board[i][j] == 0) continue;
			
			int x = i, y = j;
			while (true){
				if (x + xd[dir] < 1 || x + xd[dir] > N) break;
				if (y + yd[dir] < 1 || y + yd[dir] > N) break;
				
				int &next = board[x+xd[dir]][y+yd[dir]];
				
				if (next == 0){
					next = board[x][y];
					board[x][y] = 0;
				}
				else if (next == board[x][y] && !merge[x+xd[dir]][y+yd[dir]] && !merge[x][y]){ // merge
					board[x][y] = 0;
					next *= 2;
					merge[x+xd[dir]][y+yd[dir]] = 1;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void rightmove(){
	const int dir = 1;
	int merge[21][21] = {0, };
	for (int i = N; i >= 1; i--){
		for (int j = N; j >= 1; j--){
			if (board[i][j] == 0) continue;
			
			int x = i, y = j;
			while (true){
				if (x + xd[dir] < 1 || x + xd[dir] > N) break;
				if (y + yd[dir] < 1 || y + yd[dir] > N) break;
				
				int &next = board[x+xd[dir]][y+yd[dir]];
				
				if (next == 0){
					next = board[x][y];
					board[x][y] = 0;
				}
				else if (next == board[x][y] && !merge[x+xd[dir]][y+yd[dir]] && !merge[x][y]){ // merge
					board[x][y] = 0;
					next <<= 1;
					merge[x+xd[dir]][y+yd[dir]] = 1;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void dfs(int depth){
	int mxv = 0;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			if (mxv < board[i][j]) mxv = board[i][j];
		}
	}
	
	if (depth == 11){
		maxvalue = max(mxv, maxvalue);
		return;
	}

	if (mxv << (11-depth) <= maxvalue) return;

	
	int cboard[21][21];
	memcpy(cboard, board, sizeof(cboard));
	
	for (int i = 0; i < 4; i++){
		if (i == 0) upmove();
		if (i == 1) rightmove();
		if (i == 2) downmove();
		if (i == 3) leftmove();
		
		int check = 0;
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){
				if (board[i][j] != cboard[i][j]){
					check++; break;
				}
			}
			if (check) break;
		}
		
		if (check) dfs(depth+1);
		memcpy(board, cboard, sizeof(board));
		
	}
}

int main(){
	FASTIO;
	cin >> N;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			int t; cin >> t;
			board[i][j] = t;
			if (t > maxvalue) maxvalue = t;
		}
	}
	
	dfs(1);

	cout << maxvalue;
	
}