5번동안 상하좌우로 슬라이딩하는 작업을 했을 떄의 결과 값중 최댓값을 구하는 문제이다.

다른 골드1에 비하면 너무 쉬운 문제라 생각하는데 많은 시간이 필요하지 않았다.

대신 '슬라이딩'하는 과정에서, 필요한 만큼의 탐색만 하는 방법을 고민했다.

말 그대로 슬라이딩으로 구현하는 것이 아니라, 행이나 열을 탐색을 할 때,

 이전 값을 저장 해 주는 변수를 사용해서 같은 값이 들어오면 합쳐서 새로운 위치에 *2를 해서 넣어주고,

 아니면 변수 값을 해당 위치에 넣고 변수에 현재 값을 넣어주는 식으로 구현하여

탐색이 다 끝난 시점에서 마지막 삽입 위치부터 끝까지는 0을 넣어주는 방식으로 구현했다.

vector<vector<int>> move_down(vector<vector<int>> arr) {
	for (int i = 0; i < arr.size(); i++) {
		int new_pos = arr[i].size() - 1, prev = -1;
		for (int j = arr[i].size() - 1; j >= 0; j--) {
			if (arr[j][i] == 0) continue;
			if (prev == -1)
				prev = arr[j][i];
			else if (prev == arr[j][i]) {
				arr[new_pos--][i] = prev * 2;
				prev = -1;
			}
			else {
				arr[new_pos--][i]= prev;
				prev = arr[j][i];
			}
		}
		if (prev != -1)
			arr[new_pos--][i] = prev;
		for (int j = new_pos; j >= 0; j--)
			arr[j][i] = 0;
	}

	return arr;
}

5번의 슬라이딩 방향을 탐색하는 건 정말 단순한 DFS로 구현했다.

int dfs(int cur, vector<vector<int>> arr) {
	int max = 0;
	if (cur == max_try) {
		return get_max(arr);
	}
	vector<int> dfs_result;
	dfs_result.push_back(dfs(cur+1, move_left(arr)));
	dfs_result.push_back(dfs(cur+1, move_right(arr)));
	dfs_result.push_back(dfs(cur+1, move_up(arr)));
	dfs_result.push_back(dfs(cur+1, move_down(arr)));

	for(auto &item : dfs_result)
		if(max < item)
			max = item;

	return max;
}

아쉬운 점은 두가지 있다.

1. move 해주는 코드를 하나로 통일하고 싶음

아예 같은 역할을 하는 코드들인데, 행인지 열인지, 오름차순인지 내림차순인지로 인해 함수를 4개로 나눴다.

처리를 하기 전에 컨테이너에 담고, 그 컨테이너를 넘겨주는 식으로 구현하면 핵심 부분은 하나로 통일 할 수 있을텐데

컨테이너을 거쳐서 처리하면 추가적인 부하가 생기기 떄문에 생각으로만 남겨두었다.

공간복잡도와 시간복잡도를 희생하지 않을 좋은 방법이 있다면 그것으로 대체하고 싶을 정도로 코드가 지저분하다.

2. 공간복잡도를 더 고려할 방법은 없을까

일반적으로 재귀호출을 처리할 떄, 값들을 reference로 넘겨주는 편인데, 단순 변수가 아닌 2차원 배열을 계속 복사하여 전달해주는 것이 공간복잡도면에서 굉장한 비효율이라고 생각했다.

내가 다른 DFS 문제에서 구현할 때는 재귀 밖으로 나왔을 떄 아래에서 다시 원래 상태로 복원해 주곤 했는데, 결국 그렇게 하면 시간복잡도와 공간복잡도 간의 tradeoff가 되어 먼저 제출을 하고 공간복잡도를 초과하면 해당 방식을 시도해볼까 했는데, 그대로 통과하여 수정하지 않았다.