★ [Brute Force - 비트마스크] 2048 (Easy)

예제 입력 1

3

2 2 2

4 4 4

8 8 8

예제 출력 1

16

 

 

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

12100번: 2048 (Easy)

 

- 최대 5회 이므로, 각 이동케이스를 길이가 5인 4진법 수 4개로 변환해 각각의 경우를 모두 수행한다.

 

- 직접 풀어볼 것.

 

[ 모범 답안 (출처 : code.plus 알고리즘 중급 강의) ]

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

const int LIMIT = 5;

vector<int> gen(int k)
{
	vector<int> a(LIMIT);

	for (int i = 0; i < LIMIT; i++)
	{
		a[i] = (k & 3);
		k >>= 2;
	}

	return a;
}

int check(vector<vector<int>>& a, vector<int>& dirs)
{
	int n = a.size();

	// 합쳐졌는지 여부와 게임판을 함께 저장
	vector<vector<pair<int, bool>>> d(n, vector<pair<int, bool>>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			d[i][j].first = a[i][j];
		}
	}

	// 0 : down, 1 : up, 2 : left, 3 : right
	for (int dir : dirs)
	{
		bool ok = false;

		// 합쳐졌는지 여부 초기화
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				d[i][j].second = false;
			}
		}

		while (true) // 더이상 안움직일때까지 한 칸씩 움직인다.
		{
			ok = false;

			if (dir == 0) // 아래 방향, 합쳐질때 아래부터 합쳐지므로 아래부터 Loop
			{
				for (int i = n - 2; i >= 0; i--)
				{
					for (int j = 0; j < n; j++)
					{
						if (d[i][j].first == 0) continue; // 숫자가 없으면 그냥 지나감
						if (d[i + 1][j].first == 0) // 이동 방향이 비어있다.
						{
							d[i + 1][j].first = d[i][j].first;
							d[i + 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i + 1][j].first == d[i][j].first) // 같은숫자. 합쳐짐
						{
							// 합쳐진적 없으면
							if (d[i][j].second == false && d[i + 1][j].second == false)
							{
								d[i + 1][j].first *= 2;
								d[i + 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 1) {
				for (int i = 1; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (d[i][j].first == 0) continue;
						if (d[i - 1][j].first == 0) {
							d[i - 1][j].first = d[i][j].first;
							d[i - 1][j].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i - 1][j].first == d[i][j].first) {
							if (d[i][j].second == false && d[i - 1][j].second == false) {
								d[i - 1][j].first *= 2;
								d[i - 1][j].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 2) {
				for (int j = 1; j < n; j++) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j - 1].first == 0) {
							d[i][j - 1].first = d[i][j].first;
							d[i][j - 1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j - 1].first == d[i][j].first) {
							if (d[i][j].second == false && d[i][j - 1].second == false) {
								d[i][j - 1].first *= 2;
								d[i][j - 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}
			else if (dir == 3)
			{
				for (int j = n - 2; j >= 0; j--) {
					for (int i = 0; i < n; i++) {
						if (d[i][j].first == 0) continue;
						if (d[i][j + 1].first == 0) {
							d[i][j + 1].first = d[i][j].first;
							d[i][j + 1].second = d[i][j].second;
							d[i][j].first = 0;
							ok = true;
						}
						else if (d[i][j + 1].first == d[i][j].first) {
							if (d[i][j].second == false && d[i][j + 1].second == false) {
								d[i][j + 1].first *= 2;
								d[i][j + 1].second = true;
								d[i][j].first = 0;
								ok = true;
							}
						}
					}
				}
			}

			if (ok == false) break; // 더이상 이동할 수 없다.
		}
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans < d[i][j].first) {
				ans = d[i][j].first;
			}
		}
	}
	return ans;
}

int main(void)
{
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}

	int ans = 0;
	for (int k = 0; k < (1 << (LIMIT * 2)); k++)
	{
		vector<int> dir = gen(k);
		int cur = check(a, dir);

		if (ans < cur) ans = cur;
	}

	cout << ans << '\n';

	return 0;
}