[BOJ] 12100 : 2048(Easy) - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 백트레킹을 이용해서 4개의 방향에 대해서 총 5번 어떤 방향으로 블록을 합칠지 경우의 수를 구한다.

2. 블록을 합치는 함수를 구현한다. 이때, 블록을 합치는 방향은 위로 통일한다.

- 1) 빈 공간이 있으면 빈 공간을 다 shift 한다.

- 2) 같은 값이 있으면 블록을 합쳐준다.

- 3) 블록을 합치는 과정에서 생긴 빈 공간을 다시 shift 한다.

3. 블록을 위로만 합칠 것이므로, 1번에서 구한 방향에 맞춰 Map을 회전한 후 블록을 합친다.

4. 5번 블록을 합쳤으면, 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, map[20][20] = {}, ans = -1;

void getScore(int tempMap[20][20]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			ans = max(ans, tempMap[i][j]);
	return;
}

void move(int tempMap[20][20]) {
	// 공백을 없애자.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (tempMap[i][j] == 0) {
				int k = i, jump = 0;
				while (k < N && tempMap[k][j] == 0) {
					jump++;
					k++;
				}
				for (int k = i; k + jump < N; k++)
					tempMap[k][j] = tempMap[k + jump][j];
				for (int k = N - 1; k >= N - jump; k--)
					tempMap[k][j] = 0;
			}
		}
	}
	// 합치자.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N - 1; i++) {
			if (tempMap[i][j] == tempMap[i + 1][j]) {
				tempMap[i][j] *= 2;
				tempMap[i + 1][j] = 0;
			}
		}
	}
	// 다시 공백 없애기.
	for (int j = 0; j < N; j++) {
		for (int i = 0; i < N; i++) {
			if (tempMap[i][j] == 0) {
				int k = i, jump = 0;
				while (k < N && tempMap[k][j] == 0) {
					jump++;
					k++;
				}
				for (int k = i; k + jump < N; k++)
					tempMap[k][j] = tempMap[k + jump][j];
				for (int k = N - 1; k >= N - jump; k--)
					tempMap[k][j] = 0;
			}
		}
	}
}

void changeMap(int tempMap[20][20], int dir) {
	int dumpMap[20][20] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dumpMap[i][j] = tempMap[i][j];

	if (dir == 0) { //왼쪽
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - j][i];
	}
	else if (dir == 1) { //아래쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - i][j];

	}
	else if (dir == 2) { //오른쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}

	move(tempMap);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			dumpMap[i][j] = tempMap[i][j];

	if (dir == 0) { //왼쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}
	else if (dir == 1) { //아래쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[N - 1 - i][j];
	}
	else if (dir == 2) { //오른쪽
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempMap[i][j] = dumpMap[j][N - 1 - i];
	}

	return;
}
void playGame(vector<int> v) {
	int tempMap[20][20] = {};
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tempMap[i][j] = map[i][j];
	for (int i = 0; i < 5; i++) {
		changeMap(tempMap, v[i]);
	}
	getScore(tempMap);
	return;
}

void BT(vector<int> v) {
	if (v.size() == 5) {
		playGame(v);
		return;
	}
	for (int i = 0; i < 4; i++) {
		v.push_back(i);
		BT(v);
		v.pop_back();
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	vector<int> v;
	BT(v);

	cout << ans;

	return 0;
}

---

다음 번에는 코드를 개선해보자,,,,!!