[백준] 12100번 2048 Easy (C++, 삼성 기출)

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

배열의 얕은 복사와 깊은 복사를 더 공부하게 해주는 문제였다.
문제에 합치는 부분에서 문제를 잘못읽어서 많이 헤멨다..😂
알고리즘은 완전 탐색을 이용해 풀었다.

1. 현재 map을 카피해 cp에 저장 (깊은 복사)
2. 재귀를 통해 상, 하, 좌, 우로 움직임
3. depth가 5가 되면 return

상, 하, 좌, 우로 움직일 때 배열의 원소들을 합쳐야하는데, 이 과정에서 stack 자료구조를 사용했다.

합치는 방향에서 처음 시작하는 원소부터 stack에 삽입한 뒤, 다음 원소가 같으면 합쳐주고 flag를 true로 바꿔줘서 합치지 못하게 했다.

다음 원소를 삽입할 때 flag를 false로 바꿔줘서 새 원소가 들어왔을 때, 합칠 수 있게끔 만들어줬다.

map은 0으로 초기화해주고 for문이 끝났을 때, stack에 있는 원소들을 꺼내면서 map에 삽입해주면 끝!

#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

int n;
int **map;
int ans = 0;

void move(int ** map, int dir) {
	if(dir == 0){
		// left
		for (int i = 0; i < n; i++) {
			bool check = false;
			stack<int> s;
			for (int j = 0; j < n; j++) {
				if (map[i][j] != 0) {
					if (!s.empty() && !check) {
						int cur = s.top();
						if (cur == map[i][j]) {
							s.pop();
							int sum = cur + map[i][j];
							if (sum > ans) ans = sum;
							s.push(sum);
							check = true;
						}
						else
							s.push(map[i][j]);
					}
					else {
						check = false;
						s.push(map[i][j]);
					}
				}
				map[i][j] = 0;
			}
			while (!s.empty()) {
				map[i][s.size() - 1] = s.top();
				s.pop();
			}
		}
	}
	else if (dir == 1) {
		// up
		for (int i = 0; i < n; i++) {
			bool check = false;
			stack<int> s;
			for (int j = 0; j < n; j++) {
				if (map[j][i] != 0) {
					if (!s.empty() && !check) {
						int cur = s.top();
						if (cur == map[j][i]) {
							s.pop();
							int sum = cur + map[j][i];
							if (sum > ans) ans = sum;
							s.push(sum);
							check = true;
						}
						else
							s.push(map[j][i]);

					}
					else {
						check = false;
						s.push(map[j][i]);
					}
				}
				map[j][i] = 0;
			}
			while (!s.empty()) {
				map[s.size() - 1][i] = s.top();
				s.pop();
			}
		}
	}
	else if (dir == 2) {
		// right
		for (int i = n - 1; i >= 0; i--) {
			bool check = false;
			stack<int> s;
			for (int j = n - 1; j >= 0; j--) {
				if (map[i][j] != 0) {
					if (!s.empty() && !check) {
						int cur = s.top();
						if (cur == map[i][j]) {
							s.pop();
							int sum = cur + map[i][j];
							if (sum > ans) ans = sum;
							s.push(sum);
							check = true;
						}
						else
							s.push(map[i][j]);

					}
					else {
						check = false;
						s.push(map[i][j]);
					}
				}
				map[i][j] = 0;
			}
			while (!s.empty()) {
				map[i][n - s.size()] = s.top();
				s.pop();
			}
		}
	}

	else if (dir == 3){
		// down
		for (int i = n - 1; i >= 0; i--) {
			bool check = false;
			stack<int> s;
			for (int j = n - 1; j >= 0; j--) {
				if (map[j][i] != 0) {
					if (!s.empty() && !check) {
						int cur = s.top();
						if (cur == map[j][i]) {
							s.pop();
							int sum = cur + map[j][i];
							if (sum > ans) ans = sum;
							s.push(sum);
							check = true;
						}
						else
							s.push(map[j][i]);

					}
					else {
						check = false;
						s.push(map[j][i]);
					}
				}
				map[j][i] = 0;
			}
			while (!s.empty()) {
				map[n - s.size()][i] = s.top();
				s.pop();
			}
		}
	}
}

void copy(int** src, int** dst) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dst[i][j] = src[i][j];
}

void solve(int** m, int depth) {
	if (depth == 5) return;
	int** cp;
	cp = new int* [n];
	for (int i = 0; i < n; i++)
		cp[i] = new int[n];
	for (int i = 0; i < 4; i++) {
		copy(m, cp);
		move(cp, i);
		solve(cp, depth + 1);
	}
}

int main() {
	cin >> n;
	map = new int* [n]; 
	for(int i = 0; i < n; i++) 
		map[i] = new int[n];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			ans = max(map[i][j], ans);
		}
	}
	solve(map, 0);
	cout << ans;
}