[백준 12100번 - 2048(Easy)] C++ 풀이

백준 12100번.

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

12100번: 2048 (Easy)

예전에 많이 했던 게임인데 반갑네..

그 게임과는 다르게, 블록이 새로 추가되거나 하지는 않고, 주어진 블록들을 가지고 같은 숫자 만나면 합치고 합쳐서 최대 5번까지 이동했을 때 최대 숫자를 출력하는 문제이다.

 

사용한 알고리즘

- 시뮬레이션

- dfs

- 구현

 

음.. 또 다 해봐야지.. 라는 생각밖에 안들었다. 백트래킹으로 promising 하지 않는 경우의 수를 가지치기 할 수 있으면 효율이 더 좋아질것같다. 뭐, promising 조건으로 생각나는건, 같은 숫자가 연속으로 있지 않아서 합칠 수 없는 경우? 정도가 될 것 같다.

우선은 그냥 최대 5번 움직이라고 했으니 무조건 count 가 5가 되면 최대값 계산하는 방식으로 구현하였다. 

 

shift 함수에서는 k 값에 따라 왼/위/오/아 로 밀고 합칠 수 있는 블록을 합쳐 그 map 을 반환하는 함수이다.

2차원 벡터 v에 합칠 방향에 따라 map 에서 0이아닌 값을 push_back 한다. 그리고 합칠 수 있는 블록을 찾아서 합치고, 다시 v 를 map 에 민 방향에 맞게 대입하고 빈 부분은 0으로 채운다. v 를 새로 만든 이유는, 한 방향으로 밀고 나서, 서로 합쳐진 블록중 하나 없애야 하는데 이 작업을 그대로 map 에 하게되면 너어무 복잡해질 것 같아 v를 만들고 해당 인덱스는 erase해주는 방식을 이용했다.

dfs 이용해서 방향에 따라 shift 함수를 재귀적으로 호출하고, count == 5 이면 반환한다.

해당 열이나 행에 0만 있는 경우에 v 에 0을 push 해줘야 하는데 그 경우를 고려 안해서 한번 틀렸다.. 

코드가 조금 많이 길고 더럽다ㅜㅜ

 

완성된 코드

#include <stdio.h>
#include <vector>

using namespace std;

int n;
int ans = 0;

vector<vector<int>> shift(int k, vector<vector<int>> map) {
	vector<vector<int>> v;
	v.assign(n + 1, vector<int>());

	if (k == 0) { // 왼쪽으로 밀기
		for(int i = 0; i < n; ++i) {
			bool isAllZero = true;
			for(int j = 0; j < n; ++j) {
				if (map[i][j] != 0) {
					v[i].push_back(map[i][j]);
					isAllZero = false;
				}
			}
			if (isAllZero) {
				v[i].push_back(0);
			}
		}
	} else if (k == 1) { // 오른쪽으로 밀기
		for(int i = 0; i < n; ++i) {
			bool isAllZero = true;
			for(int j = n - 1; j >= 0 ; --j) {
				if (map[i][j] != 0) {
					v[i].push_back(map[i][j]);
					isAllZero = false;
				}
			}
			if (isAllZero) {
				v[i].push_back(0);
			}
		}
	} else if (k == 2) { // 위로 밀기
		for(int j = 0; j < n; ++j) {
			bool isAllZero = true;
			for(int i = 0; i < n; ++i) {
				if (map[i][j] != 0) {
					v[j].push_back(map[i][j]);
					isAllZero = false;
				}
			}
			if (isAllZero) {
				v[j].push_back(0);
			}
		}
	} else if (k == 3) { // 아래로 밀기
		for(int j = 0; j < n ; ++j) {
			bool isAllZero = true;
			for(int i = n - 1; i >= 0; --i) {
				if (map[i][j] != 0) {
					v[j].push_back(map[i][j]);
					isAllZero = false;
				}
			}
			if (isAllZero) {
				v[j].push_back(0);
			}
		}
	}

	for(int i = 0; i < n; ++i) {
		int temp = v[i][0];
		for(int j = 1; j < v[i].size(); ++j) {
			if (v[i][j] == 0)
				break;
			else if (temp == v[i][j]) {
				v[i][j - 1] = temp * 2;
				vector<int>::iterator it = v[i].begin();
				v[i].erase(it + j);
				temp = v[i][j]; // 다음걸로 갱신
			} else {
				temp = v[i][j];
			}
		}
	}

	if (k == 0) {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < v[i].size(); ++j) {
				map[i][j] = v[i][j];
			}
			for(int j = v[i].size(); j < n; ++j) {
				map[i][j] = 0;
			}
		}
	}
	else if (k == 1) {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < v[i].size(); ++j) {
				map[i][n - 1 - j] =v[i][j];
			}
			for(int j = v[i].size(); j < n; ++j) {
				map[i][n - 1 - j] = 0;
			}
		}
	}
	else if (k == 2) {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < v[i].size(); ++j) {
				map[j][i] = v[i][j];
			}
			for(int j = v[i].size(); j < n; ++j) {
				map[j][i] = 0;
			}
		}
	}
	else if (k == 3) {
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < v[i].size(); ++j) {
				map[n - 1 - j][i] = v[i][j];
			}
			for(int j = v[i].size(); j < n; ++j) {
				map[n - 1 - j][i] = 0;
			}
		}
	}
	return map;
}

void dfs(int cnt, vector<vector<int>> map) {
	if (cnt == 5) {
		// 해당 map 에서의 최대값 구하기
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				if (ans < map[i][j]) {
					ans = map[i][j];
				}
			}
		}
		return;
	} else {
		for(int i = 0; i < 4; ++i) {
			dfs(cnt + 1, shift(i, map));
		}
	}
}

int main() {
	scanf("%d", &n);
	vector<vector<int>> map;

	map.assign(n + 1, vector<int>(n + 1, 0));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			scanf("%d", &map[i][j]);
		}
	}

	//최대 5번 움직인다.
	dfs(0, map);

	printf("%d\n", ans);
	return 0;
}