BOJ 12100 | 2048 (Easy)

음... 4방향 전부 각기 다른 함수로 구현해야 해서 조금 짜증나는 구현이었다.

실수했던 부분은 한 움직임에서는 merge된 블럭이 다시 merge할 수 없다는 점을 간과한 것이다.

그것 말고는 dfs 써서 그냥 구현해주면 된다.

코드

#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};

void leftmove(int board[][21]){
	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;
					if (next > maxvalue) maxvalue = next;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void upmove(int board[][21]){
	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;
					if (next > maxvalue) maxvalue = next;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void downmove(int board[][21]){
	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;
					if (next > maxvalue) maxvalue = next;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void rightmove(int board[][21]){
	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 *= 2;
					merge[x+xd[dir]][y+yd[dir]] = 1;
					if (next > maxvalue) maxvalue = next;
				}
				else{
					break;
				}
				
				x+=xd[dir]; y+=yd[dir];
			}
		}
	}
}

void dfs(int depth, int board[][21], int dir){
	if (depth == 6) return;
	
	if (dir == 0) upmove(board);
	if (dir == 1) rightmove(board);
	if (dir == 2) downmove(board);
	if (dir == 3) leftmove(board);
	
	for (int i = 0; i < 4; i++){
		int cboard[21][21] = {0, };
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){
				cboard[i][j] = board[i][j];
			}
		}
		dfs(depth+1, cboard, i);
	}
}

int main(){
	cin >> N;
	int board[21][21];
	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;
		}
	}
	
	/*upmove(board);
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			debug << board[i][j] << ' ';
		}
		debug << endl;
	}*/
	
	for (int i = 0; i < 4; i++){
		int cboard[21][21] = {0, };
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){
				cboard[i][j] = board[i][j];
			}
		}
		dfs(1, cboard, i);
	}

	cout << maxvalue;
	
}