[BOJ] #12100 _ 2048(Easy)

[2048 (Easy)] https://www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

2048 게임에서 5번의 이동 후의 최대 값을 구하는 문제이다.

dfs를 이용하여, 5번으로 이동할 수 있는 모든 경우의 수를 고려하여 최대 값을 구하였다.

단, 한 번의 이동에서 합쳐진 블록은 다시 합쳐지지 않는다는 것을 유의하자!

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#define MAX 21
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

using namespace std;

int N, result, map[MAX][MAX], tmp_map[MAX][MAX];
int set_dir[6];

void solve(int idx, int dir);
void moveBlock(int dir);
void copyMap();
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
			result = (result < map[i][j]) ? map[i][j] : result;
		}
	}

	for (int i = 1; i <= 4; i++) {
		solve(1, i);
	}

	printf("%d\n", result);

	return 0;
}

void solve(int idx, int dir) {
	set_dir[idx] = dir;
	if (idx >= 5) {
		copyMap();
		for (int i = 1; i <= 5; i++) {
			moveBlock(set_dir[i]);
		}
		return;
	}

	for (int i = 0; i <= 4; i++) {
		solve(idx + 1, i);
	}
}

void moveBlock(int dir) {
	switch (dir) {
	case UP:
		for (int i = 1; i <= N; i++) {
			int idx = 1, pre = 0;
			for (int j = 1; j <= N; j++) {
				if (tmp_map[j][i] > 0) {
					if (!pre) pre = tmp_map[j][i];
					else {
						if (pre == tmp_map[j][i]) {
							tmp_map[idx++][i] = pre * 2;
							result = max(result, pre * 2);
							pre = 0;
						}
						else {
							tmp_map[idx++][i] = pre;
							pre = tmp_map[j][i];
						}
					}
					tmp_map[j][i] = 0;
				}
			}
			tmp_map[idx][i] = pre;
		}
		break;
	case DOWN:
		for (int i = N; i > 0; i--) {
			int idx = N, pre = 0;
			for (int j = N; j > 0; j--) {
				if (tmp_map[j][i] > 0) {
					if (!pre) pre = tmp_map[j][i];
					else {
						if (pre == tmp_map[j][i]) {
							tmp_map[idx--][i] = pre * 2;
							result = max(result, pre * 2);
							pre = 0;
						}
						else {
							tmp_map[idx--][i] = pre;
							pre = tmp_map[j][i];
						}
					}
					tmp_map[j][i] = 0;
				}
			}
			tmp_map[idx][i] = pre;
		}
		break;
	case LEFT:
		for (int i = 1; i <= N; i++) {
			int idx = 1, pre = 0;
			for (int j = 1; j <= N; j++) {
				if (tmp_map[i][j] > 0) {
					if (!pre) pre = tmp_map[i][j];
					else {
						if (pre == tmp_map[i][j]) {
							tmp_map[i][idx++] = pre * 2;
							result = max(result, pre * 2);
							pre = 0;
						}
						else {
							tmp_map[i][idx++] = pre;
							pre = tmp_map[i][j];
						}
					}
					tmp_map[i][j] = 0;
				}
			}
			tmp_map[i][idx] = pre;
		}
		break;
	case RIGHT:
		for (int i = N; i > 0; i--) {
			int idx = N, pre = 0;
			for (int j = N; j > 0; j--) {
				if (tmp_map[i][j] > 0) {
					if (!pre) pre = tmp_map[i][j];
					else {
						if (pre == tmp_map[i][j]) {
							tmp_map[i][idx--] = pre * 2;
							result = max(result, pre * 2);
							pre = 0;
						}
						else {
							tmp_map[i][idx--] = pre;
							pre = tmp_map[i][j];
						}
					}
					tmp_map[i][j] = 0;
				}
			}
			tmp_map[i][idx] = pre;
		}
		break;
	}
}

void copyMap() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			tmp_map[i][j] = map[i][j];
		}
	}
}