[삼성 SW 역량 테스트 기출] 2048(Easy)

12100번: 2048 (Easy)

- 이것도 강의 들으면서 풀었던 문제인데, 한번 더 풀어봤다. 확실히 모범 답안을 보고 정리하고 넘어가면 직접 짠 게 아니라 기억에 많이 남지가 않는다. 처음부터 차근차근 짜면서 복습하고 넘어갈 수 있는 기회였다.

-

- 보드의 크기는 N*N이고 N은 20이하의 자연수다. 그리 큰 수가 아니니 오버를 걱정할 필요는 없겠다.

- 주요 규칙을 정리하면,

 

한번 이동할 때 전체 블록을 상,하,좌,우 중 하나로 전부 이동시킨다.

같은 값을 갖는 블록이 충돌하면 하나로 합쳐진다. (ex. 2 2 <- 4 / 4 4 <- 8)

블록은 한번 이동할 때 한번씩만 합체 가능하다.

같은 수가 세 개 있는 경우, 이동하려는 쪽의 칸이 먼저 합쳐진다.

 

- 0은 빈칸이며, 블록에 쓰여진 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱 꼴이다. 최대 5번의 이동이 가능하다고 할 때, 얻을 수 있는 가장 큰 블록을 구하면 된다.

- 보드의 최대 크기가 얼마 되지 않으니, 이동 후의 보드 정보와 이동 횟수를 queue에 담아 bfs를 사용하면 될 것 같다. 블록이 합쳐지는 부분을 구현하는 것이 핵심이었다. 이동 방향에 따라 블록의 위치가 계속 바뀌므로, 크기가 같고 0으로 초기화된 배열(next)을 선언해 이동할 때마다 이동 후의 정보를 따로 저장했다.

- 합체는 이동 방향 쪽의 칸이 우선한다는 조건이 있으므로, 이동 방향 쪽부터 차례로 블록을 확인해간다. prev는 이전에 위치한 수를, idx는 이동한 수를 저장할 인덱스로 생각했다. 구현은 아래와 같이 했다.

 

반복문을 돌면서 prev가 -1이라면 처음 등장한 수이거나 아님 이미 합체가 이뤄진 뒤에 온 수이므로 현재 수를 prev에 저장한다.

prev가 -1이 아니고, 현재 수와 prev가 같다면 합칠 수 있는 조건이므로 next의 idx 위치에 prev*2를 저장한다. prev는 -1로 초기화하고, idx를 적절히 이동해준다. 만약 현재 수와 같지 않다면 합칠 수 없는 조건이므로 next의 idx 위치에 prev를 저장한다. prev에 현재 수를 넣어지고, idx를 적절히 이동해준다.

반복문을 다 돌고, prev가 -1이 아니면 합체하지 않고 남은 수이므로, 그 수를 next의 idx 위치에 마저 넣어준다.

 

  - 하나 주의할 점은 최대 5번까지 이동하면서 얻을 수 있는 최댓값이므로, 5번까지 이동하고 최댓값을 생각해주는 것이 아니라, 모든 경우에서 최댓값을 체크해줘야 한다는 거다. 예를 들어 아무 합체도 할 수 없는 정보가 주어진다면 그냥 그 상태에서 최댓값을 구해줘야 한다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
using namespace std;

int n;
vector<vector<int>> a;
int ans = 2;

void findMax(vector<vector<int>> &temp) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (ans < temp[i][j]) ans = temp[i][j];
		}
	}
}

void bfs() {
	queue<pair<vector<vector<int>>, int>> q; // 보드 정보와 이동 횟수
	q.push(make_pair(a, 0));
	while (!q.empty()) {
		vector<vector<int>> temp;
		int cnt;
		tie(temp, cnt) = q.front();
		q.pop();
		findMax(temp); // 최댓값 갱신
		if (cnt == 5) continue; // 최대 5번까지 이동
		for (int i = 0; i < 4; i++) {
			vector<vector<int>> next(n, vector<int>(n, 0)); // 이동한 보드 정보 저장
			if (i == 0) { // 위로 이동
				for (int j = 0; j < n; j++) { // 가로
					int prev = -1;
					int idx = 0; // 위쪽부터
					for (int k = 0; k < n; k++) { // 세로
						if (temp[k][j] != 0) {
							if (prev == -1) {
								prev = temp[k][j];
							}
							else {
								if (temp[k][j] == prev) {
									next[idx][j] = prev * 2;
									idx += 1; prev = -1;
								}
								else {
									next[idx][j] = prev;
									idx += 1; prev = temp[k][j];
								}
							}
						}
					}
					if (prev != -1) next[idx][j] = prev;
				}
			}
			else if (i == 1) { // 아래로 이동
				for (int j = 0; j < n; j++) { // 가로
					int prev = -1;
					int idx = n-1; // 아래쪽부터
					for (int k = n-1; k >= 0; k--) { // 세로
						if (temp[k][j] != 0) {
							if (prev == -1) {
								prev = temp[k][j];
							}
							else {
								if (temp[k][j] == prev) {
									next[idx][j] = prev * 2;
									idx -= 1; prev = -1;
								}
								else {
									next[idx][j] = prev;
									idx -= 1; prev = temp[k][j];
								}
							}
						}
					}
					if (prev != -1) next[idx][j] = prev;
				}
			}
			else if (i == 2) { // 왼쪽으로 이동
				for (int j = 0; j < n; j++) { // 세로
					int prev = -1;
					int idx = 0; // 왼쪽부터
					for (int k = 0; k < n; k++) { // 가로
						if (temp[j][k] != 0) {
							if (prev == -1) {
								prev = temp[j][k];
							}
							else {
								if (temp[j][k] == prev) {
									next[j][idx] = prev * 2;
									idx += 1; prev = -1;
								}
								else {
									next[j][idx] = prev;
									idx += 1; prev = temp[j][k];
								}
							}
						}
					}
					if (prev != -1) next[j][idx] = prev;
				}
			}
			else { // 오른쪽으로 이동
				for (int j = 0; j < n; j++) { // 세로
					int prev = -1;
					int idx = n-1; // 오른쪽부터
					for (int k = n-1; k >= 0; k--) { // 가로
						if (temp[j][k] != 0) {
							if (prev == -1) {
								prev = temp[j][k];
							}
							else {
								if (temp[j][k] == prev) {
									next[j][idx] = prev * 2;
									idx -= 1; prev = -1;
								}
								else {
									next[j][idx] = prev;
									idx -= 1; prev = temp[j][k];
								}
							}
						}
					}
					if (prev != -1) next[j][idx] = prev;
				}
			}
			if (next != temp) q.push(make_pair(next, cnt + 1)); // 변화가 있으면 저장
		}

	}
	return;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int> t(n);
		for (int j = 0; j < n; j++) {
			cin >> t[j];
		}
		a.push_back(t);
	}

	bfs();
	cout << ans << '\n';
	return 0;
}