2048 (Easy) (feat. 백준, 12100번)

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

12100번: 2048 (Easy)

반응형

// woohyeon.kim
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int dx[4], dy[4];
int boards[21][21];
int tmp[21][21];
int result;
vector<int> directions;

void pour(int direction)
{
	if (direction == 0)
	{
		// 북쪽으로 쏟기
		for (auto ix = 0; ix < N; ++ix)
		{
			for (auto iy = 0; iy < N; ++iy)
			{
				if (tmp[ix][iy] != 0)
				{
					auto tmp_ix = ix;
					while ((tmp_ix - 1) >= 0)
					{
						if (tmp[tmp_ix - 1][iy] == 0)
						{
							tmp[tmp_ix - 1][iy] = tmp[tmp_ix][iy];
							tmp[tmp_ix][iy] = 0;
							--tmp_ix;
						}
						else
							break;
					}
				}
			}
		}
	}
	else if (direction == 2)
	{
		// 남쪽으로 쏟기
		for (auto ix = N - 1; ix >= 0; --ix)
		{
			for (auto iy = 0; iy < N; ++iy)
			{
				if (tmp[ix][iy] != 0)
				{
					auto tmp_ix = ix;
					while ((tmp_ix + 1) < N)
					{
						if (tmp[tmp_ix + 1][iy] == 0)
						{
							tmp[tmp_ix + 1][iy] = tmp[tmp_ix][iy];
							tmp[tmp_ix][iy] = 0;
							++tmp_ix;
						}
						else
							break;
					}
				}
			}
		}
	}
	else if (direction == 3)
	{
		// 서로 쏟기
		for (auto iy = 0; iy < N; ++iy)
		{
			for (auto ix = 0; ix < N; ++ix)
			{
				if (tmp[ix][iy] != 0)
				{
					auto tmp_iy = iy;
					while ((tmp_iy - 1) >= 0)
					{
						if (tmp[ix][tmp_iy - 1] == 0)
						{
							tmp[ix][tmp_iy - 1] = tmp[ix][tmp_iy];
							tmp[ix][tmp_iy] = 0;
							--tmp_iy;
						}
						else
							break;
					}
				}
			}
		}
	}
	else
	{
		// 동으로 쏟기
		for (auto iy = N - 1; iy >= 0; --iy)
		{
			for (auto ix = 0; ix < N; ++ix)
			{
				if (tmp[ix][iy] != 0)
				{
					auto tmp_iy = iy;
					while ((tmp_iy + 1) < N)
					{
						if (tmp[ix][tmp_iy + 1] == 0)
						{
							tmp[ix][tmp_iy + 1] = tmp[ix][tmp_iy];
							tmp[ix][tmp_iy] = 0;
							++tmp_iy;
						}
						else
							break;
					}
				}
			}
		}
	}
}
void move(int direction)
{
	pour(direction);
	// 북쪽으로
	if (direction == 0)
	{
		for (auto ix = 0; ix < N - 1; ++ix)
		{
			for (auto iy = 0; iy < N; ++iy)
			{
				if (tmp[ix][iy] == tmp[ix + 1][iy])
				{
					tmp[ix][iy] *= 2;
					tmp[ix + 1][iy] = 0;
				}
			}
		}
	}
	// 남으로
	else if (direction == 2)
	{
		for (auto ix = N - 1; ix > 0; --ix)
		{
			for (auto iy = 0; iy < N; ++iy)
			{
				if (tmp[ix][iy] == tmp[ix - 1][iy])
				{
					tmp[ix][iy] *= 2;
					tmp[ix - 1][iy] = 0;
				}
			}
		}
	}
	// 서로
	else if (direction == 3)
	{
		for (auto iy = 0; iy < N - 1; ++iy)
		{
			for (auto ix = 0; ix < N; ++ix)
			{
				if (tmp[ix][iy] == tmp[ix][iy + 1])
				{
					tmp[ix][iy] *= 2;
					tmp[ix][iy + 1] = 0;
				}
			}
		}
	}
	// 동으로
	else
	{
		for (auto iy = N - 1; iy > 0; --iy)
		{
			for (auto ix = 0; ix < N; ++ix)
			{
				if (tmp[ix][iy] == tmp[ix][iy - 1])
				{
					tmp[ix][iy] *= 2;
					tmp[ix][iy - 1] = 0;
				}
			}
		}
	}
	pour(direction);
}

void dfs()
{
	if (directions.size() == 5)
	{
		for (auto ix = 0; ix < N; ++ix)
		{
			for (auto iy = 0; iy < N; ++iy)
				tmp[ix][iy] = boards[ix][iy];
		}
		for (const auto& direction : directions)
			move(direction);

		for (auto ix = 0; ix < N; ++ix)
		{
			for (auto iy = 0; iy < N; ++iy)
				result = max(result, tmp[ix][iy]);
		}
		return;
	}
	for (auto idx = 0; idx < 4; ++idx)
	{
		directions.push_back(idx);
		dfs();
		directions.pop_back();
	}
}

int main()
{
	dx[0] = -1, dx[1] = 0, dx[2] = 1, dx[3] = 0;
	dy[0] = 0, dy[1] = 1, dy[2] = 0, dy[3] = -1;
	cin >> N;
	memset(boards, 0, 21 * 21 * 4);
	memset(tmp, 0, 21 * 21 * 4);
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < N; ++iy)
			cin >> boards[ix][iy];
	}

	result = 0;
	dfs();

	cout << result << endl;

	return 0;
}
// *&)*@*

정말 날코딩 문제였던것 같습니다.

신경써야할 사항은 아래 정도 되겠습니다.

1. 한쪽 방향으로 모든 숫자를 쏟아준다. 즉, 사이에 0이 없이 한쪽으로 해당 행 또는 열의 값이 있어야 한다.
2. 4개의 방향으로 5가지의 순열을 구한다. 위위위위아래 / 위위위아래위 의 결과는 다를 수 있으므로 중복이 포함된 순열이다.