[C/C++] 백준 - 12100번 : 2048(Easy)

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

12100번: 2048 (Easy)

복잡해보이는 시물레이션 문제이다. 4가지의 방향이 존재하고 모든 경우의 수를 따져보아야 최대값을 알 수 있으므로 백트래킹으로 완전탐색을 해야겠다고 생각했다.

보드 안 블록을 옮기는 과정 구현하는게 가장 까다로웠다.

 

블록은 위, 아래, 양 옆으로 이동이 가능하며 총 4가지 방향이 이동가능하다.

2048게임을 해보면 알겠지만,

 

1. 어느 한 방향으로 이동했을 때 한 블록이 합쳐질 수 있는건 한 번 밖에 없다. 한 번 합쳐지고 난 후 또 같은 크기의 블록이 있다해도 합쳐진 블록은 더 이상 합쳐지는 것이 불가능하다.

->  bool 변수를 통해 합쳐진 이력이 있다면 true로 바꿔, true의 경우에는 추가적으로 블록이 합쳐지는 경우를 방지한다.

 

2. 비어있는 칸이 있는 방향으로 옮기는 경우, 블록이 있는 칸 또는 경계선 마지막으로 이동할 때까지 계속 이동한다.

예를 들어 4x4 크기의 보드에서 (1,1)에 블록이 있고 (1,2)에서 (1,4)까지 블록이 없다고 가정한 후, 오른쪽으로 이동시킬 경우 (1,1)에서 (1,2)로 가는 것이 아닌 (1,4)까지 이동한다. 또는 바로 다음 칸에 블록이 있을 때까지 계속 이동한다.

 

위에 있는 상황을 고려해서 모든 칸을 이동하는 방향으로 이동시켜주면 된다.

(1) 이동 시킬 칸이 비어있는 칸이라면? -> 아무것도 하지 않아도 된다.

(2) 이동 시킬 칸이 비어있지는 않지만 이동시킬 방향의 다음 칸이 비어있다면? -> 이동 시켜야 하는 칸 다음 칸이 블록이거나, 경계 외부가 나올 때까지 이동 시킨다. 그리고 여기서 끝이 아니라, 이동을 시킨 후 다음 칸과 같은 값인지 확인하고, 그 칸이 합쳐진 이력이 있는지 확인시켜주어 합쳐진 적이 없다면 합쳐준다.

(3) 이동 시킬 칸이 비어있지 않은 칸이며 이동 시킬 방향의 다음 칸도 비어있지 않다면? -> 값이 같은지 확인해주고,

같을 경우 그 칸에 합쳐진 이력이 있는지 확인해준다. 이력이 없는 경우 합쳐주도록 한다.

 

위 방법으로 코드를 작성해주면 된다.

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 0x7fffffff
using namespace std;
typedef long long ll;

int N, maxV;
int board[21][21];
bool visited[21][21];
int Cboard[10][21][21];

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
		}
	}
}

void Copy(int depth) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			Cboard[depth][i][j] = board[i][j];
		}
	}
}

void Reverse(int depth) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			board[i][j] = Cboard[depth][i][j];
		}
	}
}

void Down() {
	for (int i = 1; i <= N; i++) {
		for (int j = N - 1; j >= 1; j--) {
			if (board[j][i] == 0) continue;
			else {
				if (board[j + 1][i] == 0) {
					int y = j + 1;
					while (y <= N && board[y][i] == 0) {
						board[y][i] = board[y - 1][i];
						board[y - 1][i] = 0;
						y++;
					}
					if (y <= N && board[y][i] == board[y - 1][i] && !visited[y][i]) {
						visited[y][i] = true;
						board[y][i] += board[y - 1][i];
						board[y - 1][i] = 0;
					}
				}
				else {
					if (board[j][i] != board[j + 1][i]) continue;
					else {
						if (!visited[j + 1][i]) {
							visited[j + 1][i] = true;
							board[j + 1][i] += board[j][i];;
							board[j][i] = 0;
						}
					}
				}
			}
		}
	}
}

void Up() {
	for (int i = 1; i <= N; i++) {
		for (int j = 2; j <= N; j++) {
			if (board[j][i] == 0) continue;
			else {
				if (board[j - 1][i] == 0) {
					int y = j - 1;
					while (y >= 1 && board[y][i] == 0) {
						board[y][i] = board[y + 1][i];
						board[y + 1][i] = 0;
						y--;
					}
					if (y >= 1 && board[y][i] == board[y + 1][i] && !visited[y][i]) {
						visited[y][i] = true;
						board[y][i] += board[y + 1][i];
						board[y + 1][i] = 0;
					}
				}
				else {
					if (board[j][i] != board[j - 1][i]) continue;
					else {
						if (!visited[j - 1][i]) {
							visited[j - 1][i] = true;
							board[j - 1][i] += board[j][i];;
							board[j][i] = 0;
						}
					}
				}
			}
		}
	}
}

void Right() {
	for (int i = 1; i <= N; i++) {
		for (int j = N - 1; j >= 1; j--) {
			if (board[i][j] == 0) continue;
			else {
				if (board[i][j + 1] == 0) {
					int x = j + 1;
					while (x <= N && board[i][x] == 0) {
						board[i][x] = board[i][x - 1];
						board[i][x - 1] = 0;
						x++;
					}
					if (x <= N && board[i][x] == board[i][x - 1] && !visited[i][x]) {
						visited[i][x] = true;
						board[i][x] += board[i][x - 1];
						board[i][x - 1] = 0;
					}
				}
				else {
					if (board[i][j] != board[i][j + 1]) continue;
					else {
						if (!visited[i][j + 1]) {
							visited[i][j + 1] = true;
							board[i][j + 1] += board[i][j];
							board[i][j] = 0;
						}
					}
				}
			}
		}
	}
}

void Left() {
	for (int i = 1; i <= N; i++) {
		for (int j = 2; j <= N; j++) {
			if (board[i][j] == 0) continue;
			else {
				if (board[i][j - 1] == 0) {
					int x = j - 1;
					while (x >= 1 && board[i][x] == 0) {
						board[i][x] = board[i][x + 1];
						board[i][x + 1] = 0;
						x--;
					}
					if (x >= 1 && board[i][x] == board[i][x + 1] && !visited[i][x]) {
						visited[i][x] = true;
						board[i][x] += board[i][x + 1];
						board[i][x + 1] = 0;
					}
				}
				else {
					if (board[i][j] != board[i][j - 1]) continue;
					else {
						if (!visited[i][j - 1]) {
							visited[i][j - 1] = true;
							board[i][j - 1] += board[i][j];
							board[i][j] = 0;
						}
					}
				}
			}
		}
	}
}

void Move(int dir) {
	memset(visited, false, sizeof(visited));
	switch (dir) {
	case 0:
		Down();
		break;
	case 1:
		Up();
		break;
	case 2:
		Right();
		break;
	case 3:
		Left();
		break;
	}
}

int FindMaxValue() {
	int mV = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			mV = max(mV, board[i][j]);
		}
	}
	return mV;
}

void func(int depth) {
	maxV = max(maxV, FindMaxValue());
	if (depth == 5) return;

	for (int i = 0; i < 4; i++) {
		Copy(depth);
		Move(i);
		func(depth + 1);
		Reverse(depth);
	}
}

int main() {
	CUNLINK;
	Input();
	func(0);
	cout << maxV << endl;

	return 0;
}