[백준/BOJ] 백준 12100번 : 2048 (Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

Solve함수 내에서 tempboard를 만들어서 board를 움직이고 난 뒤, 움직인 board를 이전으로 되돌리는 일을 한다. board를 5번 이하로 이동시키는 경우를 모두 확인하면서 그중 가장 큰 블록의 값을 구한다.

 

코드

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

int n;
int board[20][20];
int result = -1;

//board를 복사한다
void boardCopy(int to[][20], int from[][20])
{
	for (int i = 0; i < 20; i++)
		for (int j = 0; j < 20; j++)
			to[i][j] = from[i][j];
}

//가장 큰 블록의 값을 반환한다
int maxFind(int thisboard[][20])
{
	int ret = -1;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ret = max(ret, thisboard[i][j]);

	return ret;
}

//board를 dir방향(0:왼쪽, 1:위쪽, 2:오른쪽, 3:아래쪽)으로 움직인다
void boardMove(int thisboard[][20], int dir)
{
	vector<int> moved_block;
	vector<int> changed_block;

	//왼쪽으로 움직일때
	if (dir == 0)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (thisboard[i][j] != 0)
				{
					moved_block.push_back(thisboard[i][j]);
					thisboard[i][j] = 0;
				}
			}

			for (int k = 0; k < moved_block.size();)
			{
				//moved_block의 마지막에 도달했을때
				if (k == moved_block.size() - 1)
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}

				//block이 합쳐질때
				else if (moved_block[k] == moved_block[k + 1])
				{
					changed_block.push_back(moved_block[k] * 2);
					k = k + 2;
				}

				else
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}
			}

			//옮겨져서 바뀐 블록을 고려해서 재배치 한다
			for (int k = 0; k < changed_block.size(); k++)
			{
				thisboard[i][k] = changed_block[k];
			}

			moved_block.clear();
			changed_block.clear();
		}
	}

	//위쪽으로 움직일때
	else if (dir == 1)
	{
		for (int j = 0; j < n; j++)
		{
			for (int i = 0; i < n; i++)
			{
				if (thisboard[i][j] != 0)
				{
					moved_block.push_back(thisboard[i][j]);
					thisboard[i][j] = 0;
				}
			}

			for (int k = 0; k < moved_block.size();)
			{
				if (k == moved_block.size() - 1)
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}

				else if (moved_block[k] == moved_block[k + 1])
				{
					changed_block.push_back(moved_block[k] * 2);
					k = k + 2;
				}

				else
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}
			}

			for (int k = 0; k < changed_block.size(); k++)
			{
				thisboard[k][j] = changed_block[k];
			}

			moved_block.clear();
			changed_block.clear();
		}
	}

	//오른쪽으로 움직일때
	else if (dir == 2)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = n - 1; j >= 0; j--)
			{
				if (thisboard[i][j] != 0)
				{
					moved_block.push_back(thisboard[i][j]);
					thisboard[i][j] = 0;
				}
			}

			for (int k = 0; k < moved_block.size();)
			{
				if (k == moved_block.size() - 1)
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}

				else if (moved_block[k] == moved_block[k + 1])
				{
					changed_block.push_back(moved_block[k] * 2);
					k = k + 2;
				}

				else
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}
			}

			for (int k = 0; k < changed_block.size(); k++)
			{
				thisboard[i][n - 1 - k] = changed_block[k];
			}

			moved_block.clear();
			changed_block.clear();
		}
	}

	//아래쪽으로 움직일때
	else if (dir == 3)
	{
		for (int j = 0; j < n; j++)
		{
			for (int i = n - 1; i >= 0; i--)
			{
				if (thisboard[i][j] != 0)
				{
					moved_block.push_back(thisboard[i][j]);
					thisboard[i][j] = 0;
				}
			}

			for (int k = 0; k < moved_block.size();)
			{
				if (k == moved_block.size() - 1)
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}

				else if (moved_block[k] == moved_block[k + 1])
				{
					changed_block.push_back(moved_block[k] * 2);
					k = k + 2;
				}

				else
				{
					changed_block.push_back(moved_block[k]);
					k = k + 1;
				}
			}

			for (int k = 0; k < changed_block.size(); k++)
			{
				thisboard[n - 1 - k][j] = changed_block[k];
			}

			moved_block.clear();
			changed_block.clear();
		}
	}
}

void Solve(int thisboard[][20], int cnt)
{
	//5번 이상 이동했을때
	if (cnt > 5)
		return;

	int tempboard[20][20];

	//구할 수 있는 가장 큰 블록을 찾는다
	result = max(result, maxFind(thisboard));

	//현재 board를 저장해 놓는다
	boardCopy(tempboard, thisboard);

	for (int i = 0; i < 4; i++)
	{
		//board를 움직인다
		boardMove(thisboard, i);

		Solve(thisboard, cnt + 1);

		//움직인 board를 이전으로 되돌린다
		boardCopy(thisboard, tempboard);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;

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

	Solve(board, 0);

	cout << result;

	return 0;
}