[백준 12100] 2048 (Easy)

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/2048-game/description?page=1&pageSize=20

코드트리 문제와 유사함 (TC만 다른듯!)
✔ 코드트리 2048
https://www.codetree.ai/training-field/frequent-problems/problems/2048-game/description?page=1&pageSize=20
✔ 내 풀이
https://velog.io/@rhkr9080/%EC%BD%94%EB%93%9C%ED%8A%B8%EB%A6%AC-2048-%EA%B2%8C%EC%9E%84

💻 문제 풀이 : C++

// 요구사항
// 1. 4방향 중력
//    => temp_map 만들어야 하나?
// 2. 최대값 찾기
// 3. 5번 움직일 동안 방향 선택하기
//    => 
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAP_SIZE 25

using namespace std;

int n, answer;
int MAP[MAP_SIZE][MAP_SIZE];
int ORIG_MAP[MAP_SIZE][MAP_SIZE];
vector<int> picked;

void CLEAR()
{
	n = 0;
	answer = 0;
	memset(MAP, 0, sizeof(MAP));
	memset(ORIG_MAP, 0, sizeof(ORIG_MAP));
	picked.clear();
}

// 상, 하, 좌, 우
int dr[] = {-1, 1,0 ,0};
int dc[] = {0, 0,-1, 1};

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

int getMax()
{
	int maxAns = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (maxAns < MAP[i][j])
				maxAns = MAP[i][j];
	return maxAns;
}

// 병합
void mix(int dir)
{
	// 1. 같은 숫자 확인
	for (int i = 0; i < n; i++)
	{
		int key = -1;
		for (int j = 0; j < n; j++)
		{
			if (dir == 0)
			{
				if (key == -1 && MAP[j][i] != 0)
					key = j;
				else if (key != -1 && MAP[j][i] != 0)
				{
					if (MAP[j][i] == MAP[key][i])
					{
						MAP[key][i] = MAP[j][i] * 2;
						MAP[j][i] = 0;
						key = -1;
					}
					else
					{
						key = j;
					}
				}
			}
			else if (dir == 1)
			{
				if (key == -1 && MAP[n - j - 1][i] != 0)
					key = n-j-1;
				else if (key != -1 && MAP[n - j - 1][i] != 0)
				{
					if (MAP[n - j - 1][i] == MAP[key][i])
					{
						MAP[key][i] = MAP[n - j - 1][i] * 2;
						MAP[n - j - 1][i] = 0;
						key = -1;
					}
					else
					{
						key = n-j-1;
					}
				}
			}
			else if (dir == 2)
			{
				if (key == -1 && MAP[i][j] != 0)
					key = j;
				else if (key != -1 && MAP[i][j] != 0)
				{
					if (MAP[i][j] == MAP[i][key])
					{
						MAP[i][key] = MAP[i][j] * 2;
						MAP[i][j] = 0;
						key = -1;
					}
					else
					{
						key = j;
					}
				}
			}
			else if (dir == 3)
			{
				if (key == -1 && MAP[i][n-j-1] != 0)
					key = n-j-1;
				else if (key != -1 && MAP[i][n - j - 1] != 0)
				{
					if (MAP[i][n - j - 1] == MAP[i][key])
					{
						MAP[i][key] = MAP[i][n - j - 1] * 2;
						MAP[i][n - j - 1] = 0;
						key = -1;
					}
					else
					{
						key = n-j-1;
					}
				}
			}
		}
	}
}

// 이동
void move(int dir)
{
	for (int i = 0; i < n; i++)
	{
		int tmp[MAP_SIZE] = { 0 };
		int idx = 0;
		for (int j = 0; j < n; j++)
		{
			if (dir == 0)
			{
				if (MAP[j][i])
					tmp[idx++] = MAP[j][i];
			}
			else if (dir == 1)
			{
				if (MAP[n - j - 1][i])
					tmp[idx++] = MAP[n - j - 1][i];
			}
			else if (dir == 2)
			{
				if (MAP[i][j])
					tmp[idx++] = MAP[i][j];
			}
			else if (dir == 3)
			{
				if (MAP[i][n - j - 1])
					tmp[idx++] = MAP[i][n - j - 1];
			}
		}
		for (int j = 0; j < n; j++)
		{
			if (dir == 0)
				MAP[j][i] = tmp[j];
			else if (dir == 1)
				MAP[n - j - 1][i] = tmp[j];
			else if (dir == 2)
				MAP[i][j] = tmp[j];
			else if (dir == 3)
				MAP[i][n - j - 1] = tmp[j];
		}
	}
}

void printMap()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << MAP[i][j] << " ";
		}
		cout << endl;
	}
}

void copyOrigin()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			MAP[i][j] = ORIG_MAP[i][j];
}

void dfs(int count)
{
	if (count >= 5) {
		copyOrigin();
		for (int i = 0; i < picked.size(); i++)
		{
			mix(picked[i]);
			move(picked[i]);
		}
		answer = max(answer, getMax());
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		picked.push_back(i);
		dfs(count + 1);
		picked.pop_back();
	}
}

void SOLVE()
{
	dfs(0);
	//copyOrigin();
	//mix(2);
	//printMap();
	cout << answer << "\n";
}

int main()
{
	CLEAR();
	INIT();
	SOLVE();

	return 0;
}

---

📌 memo 😊

문제가 생겼을 때 논리적 허점 찾기!!!

💥 이 문제에서의 논리적 허점!!
=> Merge가 인접한 곳이 아니라 떨어진 곳에서도 발생할 수 있다
=> 값을 기록해나가면서 비교해가기