[삼성코테기출문제]2048(Easy)

2048(Easy)

문제

게임으로 익숙한 문제이다. 상반기 코테 준비할 때 풀었던 중력문제와 느낌이 비슷했고, 구슬 탈출 2 문제와도 어찌보면 비슷하다고 생각된다.
한 쪽 방향으로 밀면 모든 숫자들이 그 방향으로 이동하는데 숫자가 같으면 합쳐주기, 심플하지만 생각보다 구현이 어려웠다.

문제풀이

처음 문제 접근할 때는 bfs dfs하는 것처럼 한 칸 한 칸 다 생각하려고 했다. 하지만 이 문제의 키포인트는 특정 방향으로 밀었을 때 먼저 계산을 해야하는 숫자들의 계산을 어떻게 할 것인가? 였다.
예를 들면 2 2 2이런식으로 같은 숫자가 연속하여 있고 왼쪽방향으로 민다면 그 방향의 가장 앞쪽에 있는 숫자부터 계산해줘야한다. 따라서 결과는 4 2 0이 되어야한다.

풀이 과정

1. 먼저 현재 맵의 상태를 복사해준다. 모든 방향에 대해서 최대 5번 시행했을때의 결과를 찾는 것이므로 현재맵에서 총 4가지 경우의 다음맵이 생기기 때문에 현재 맵의 정보가 유지되어야한다.
2. 4방향에 대하여 for문을 돌라고 해당 방향으로 밀고 난 후의 상태를 다시 복사하고 다시 확인하는 것을 재귀함수를 이용한다.
3. Move함수에서는 방향정보를 입력받고 그 방향정보에 해당하는 방향의 첫 번째부터 큐에 담는다.(FIFO를 이용하기 위하여) (예를 들어 오른쪽이면 N-1부터 맵에 숫자가 있으면 큐에 담는다)
4. 큐에 들어간 숫자들을 하나씩 꺼내고 현재 방향의 첫번째부터 맵을 확인한다. 만약 0이라면, 해당 좌표에 큐에서 꺼낸 값을 넣고, 만약 큐에서 꺼낸값과 같다면 해당 좌표에 큐에서 꺼낸 값과 해당 좌표의 값을 더해주고, 만약 둘 다 아니라면 다음 좌표에 큐에서 꺼낸값을 넣어준다.(그림)
5. 재귀함수가 호출될때마다 카운팅을하여 총 5번이 되면 해당 맵의 최대값을 찾고 재귀함수를 종료한다.
6. 위 과정을 모든방향에 대해서 5번 시행 될때까지 반복한다.

#include<iostream>
#include<queue>
using namespace std;

const int MAX_N = 20;

int N, Answer;
int Map[MAX_N][MAX_N];

void Init() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
		}
	}
}
void Move(int dir) {
	queue<int> q;
	if (dir == 0) {
		for (int i = 0, idx = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j]) q.push(Map[i][j]);
				Map[i][j] = 0;
			}
			idx = 0;
			while (!q.empty()) {
				int x = q.front();
				q.pop();

				if (!Map[i][idx])Map[i][idx] = x;
				else if (Map[i][idx] == x) {
					Map[i][idx] *= 2;
					idx++;
				}
				else {
					idx++;
					Map[i][idx] = x;
				}
			}
		}
	}
	else if (dir == 1) {
		for (int i = 0, idx = 0; i < N; i++) {
			for (int j = N - 1; j >= 0; j--) {
				if (Map[i][j]) q.push(Map[i][j]);
				Map[i][j] = 0;
			}
			idx = N - 1;
			while (!q.empty()) {
				int x = q.front();
				q.pop();

				if (!Map[i][idx])Map[i][idx] = x;
				else if (Map[i][idx] == x) {
					Map[i][idx] *= 2;
					idx--;
				}
				else {
					idx--;
					Map[i][idx] = x;
				}
			}
		}
	}
	else if (dir == 2) {
		for (int i = 0, idx = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[j][i]) q.push(Map[j][i]);
				Map[j][i] = 0;
			}
			idx = 0;
			while (!q.empty()) {
				int x = q.front();
				q.pop();

				if (!Map[idx][i])Map[idx][i] = x;
				else if (Map[idx][i] == x) {
					Map[idx][i] *= 2;
					idx++;
				}
				else {
					idx++;
					Map[idx][i] = x;
				}
			}
		}
	}
	else if (dir == 3) {
		for (int i = 0, idx = 0; i < N; i++) {
			for (int j = N - 1; j >= 0; j--) {
				if (Map[j][i]) q.push(Map[j][i]);
				Map[j][i] = 0;
			}
			idx = N - 1;
			while (!q.empty()) {
				int x = q.front();
				q.pop();

				if (!Map[idx][i])Map[idx][i] = x;
				else if (Map[idx][i] == x) {
					Map[idx][i] *= 2;
					idx--;
				}
				else {
					idx--;
					Map[idx][i] = x;
				}
			}
		}
	}
}

void Process(int n) {
	int tmp[MAX_N][MAX_N];
	if (n == 5) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				Answer = max(Answer, Map[i][j]);
		return;
	}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			tmp[i][j] = Map[i][j];
	
	for (int d = 0; d < 4; d++) {
		Move(d);
		Process(n + 1);
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				Map[i][j] = tmp[i][j];
	}
}
void Solution() {
	Init();
	Process(0);
	cout << Answer << endl;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	freopen("02.in", "r", stdin);
	Solution();
	return 0;
}