백준 2048 (Easy) 재풀이

다시 풀어도 과정은 유사하게 푼 것 같다.

다만 복원 배열을 전역으로 쓴것은 함정.

복원 값이 다음 차의 DFS에서 날라가므로 안된다.

 

 

 

#include<iostream>
#include<string.h>

using namespace std;

int arr[20][20];

bool visit[20][20];
int N;
int maxa;


void moveUp()
{
	memset(visit, 0, sizeof(visit));

	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (arr[i][j] != 0)
			{
				int index = i - 1;
				bool check = false;
				while (index >= 0)
				{
					if (arr[index][j] == 0)
					{
						index--;
					}
					else
					{
						check = true;
						if (arr[i][j] == arr[index][j] && !visit[index][j])
						{

							arr[i][j] = 0;
							arr[index][j] *= 2;
							visit[index][j] = true;


							break;
						}
						else
						{

							if (i != index + 1)
							{
								arr[index + 1][j] = arr[i][j];
								arr[i][j] = 0;


							}

							break;

						}
					}
				}
				index++;

				if (!check && i != 0)
				{
					arr[index][j] = arr[i][j];
					arr[i][j] = 0;

				}
			}
		}
	}
}

void moveDown()
{
	memset(visit, 0, sizeof(visit));

	for (int j = 0; j < N; j++)
	{
		for (int i = N - 1; i >= 0; i--)
		{
			if (arr[i][j] != 0)
			{
				int index = i + 1;
				bool check = false;
				while (index < N)
				{
					if (arr[index][j] == 0)
					{
						index++;
					}
					else
					{
						check = true;
						if (arr[i][j] == arr[index][j] && !visit[index][j])
						{

							arr[i][j] = 0;
							arr[index][j] *= 2;
							visit[index][j] = true;
							break;
						}
						else
						{

							if (i != index - 1)
							{
								arr[index - 1][j] = arr[i][j];
								arr[i][j] = 0;

							}

							break;

						}
					}
				}
				index--;

				if (!check && i != N - 1)
				{
					arr[index][j] = arr[i][j];
					arr[i][j] = 0;
				}
			}
		}
	}


}

void moveLeft()
{
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][j] != 0)
			{
				int index = j - 1;
				bool check = false;
				while (index >= 0)
				{
					if (arr[i][index] == 0)
					{
						index--;
					}
					else
					{
						check = true;
						if (arr[i][j] == arr[i][index] && !visit[i][index])
						{

							arr[i][j] = 0;
							arr[i][index] *= 2;
							visit[i][index] = true;
							break;
						}
						else
						{

							if (j != index + 1)
							{

								arr[i][index + 1] = arr[i][j];
								arr[i][j] = 0;

							}

							break;

						}
					}
				}

				index++;

				if (!check && j != 0)
				{
					arr[i][index] = arr[i][j];
					arr[i][j] = 0;
				}
			}
		}
	}


}

void moveRight()
{
	memset(visit, 0, sizeof(visit));

	for (int i = 0; i < N; i++)
	{
		for (int j = N - 1; j >= 0; j--)
		{
			if (arr[i][j] != 0)
			{
				int index = j + 1;
				bool check = false;
				while (index < N)
				{
					if (arr[i][index] == 0)
					{
						index++;
					}
					else
					{
						check = true;
						if (arr[i][j] == arr[i][index] && !visit[i][index])
						{

							arr[i][j] = 0;
							arr[i][index] *= 2;
							visit[i][index] = true;
							break;
						}
						else
						{

							if (j != index - 1)
							{
								arr[i][index - 1] = arr[i][j];
								arr[i][j] = 0;

							}

							break;


						}
					}
				}

				index--;

				if (!check && j != N - 1)
				{
					arr[i][index] = arr[i][j];
					arr[i][j] = 0;
				}
			}
		}
	}

}

void moveBack()
{
	
}

void copy()
{
	
}

int findMax()
{
	int m = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (m < arr[i][j])
			{
				m = arr[i][j];
			}
		}
	}

	return m;
}

void DFS(int cur)
{
	/*cout << "현재 " << cur << " 목표 " << pos << endl;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

	*/

	if (cur == 5)
	{
		int result = findMax();
		if (maxa < result)
		{
			maxa = result;
		}
		return;
	}

	
	int temp[20][20];

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			temp[i][j] = arr[i][j];
		}
	}

	moveUp();
	//cout << "위로 이동" << endl;
	DFS(cur + 1);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = temp[i][j];
		}
	}

	moveDown();
	//cout << "아래로 이동" << endl;
	DFS(cur + 1);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = temp[i][j];
		}
	}

	moveRight();
	//cout << "오른쪽로 이동" << endl;
	DFS(cur + 1);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = temp[i][j];
		}
	}

	moveLeft();
	//cout << "왼쪽로 이동" << endl;
	DFS(cur + 1);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			arr[i][j] = temp[i][j];
		}
	}
}


int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}

	maxa = 0;
	
	
	DFS(0);

	cout << maxa << endl;


}