백준 - 12100번 2048 - easy 문제 풀이 정리

이번에 풀어본 문제는 solved.ac 기준 class 5에 속하는 2048문제입니다.

 

다들 알고 계시는 2048게임을 5번까지 시뮬레이션했을 때 결과로 뽑아낼 수 있는 최대의 수를 찾는 문제로 원래 2048 게임은 한 번 이동이 발생할 때마다 새로운 블록이 등장하는 것과 다르게 이 문제에서는 새로운 블록이 등장하지 않는 전제 하에 시뮬레이션을 구현하면 됩니다.

 

문제 링크

12100번: 2048 (Easy)

2048 게임은 여기서 플레이 해보실 수 있습니다!

2048

---

문제 설명

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

---

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

풀이 과정 정리

우선 2048 게임의 시뮬레이션 과정을 moveBoard 함수로 구현했습니다. 이 함수는 인자로 dir(이동 방향)을 받아서 그에 따른 시뮬레이션 과정을 board 배열을 통해 진행합니다.

 

기존에는 값의 깊은 복사를 통해서 이동 과정을 구현했는데, 중간에 실수가 발생해서 아예 새로 갈아 엎어 queue를 사용해서 새로 이동 과정을 구현했습니다.

 

queue를 이용해 0이 아닌 값들을 순차적으로 담고, idx라는 변수로 해당 방향으로 이동 동작을 수행했을 때, 값이 들어가는 위치를 기록하는 방식으로 구현했습니다.

 

그래서 queue에서 뽑아온 값이 현재 가리키고 있는 값과 같다면 2배로 만들고, 다르다면 queue에서 뽑아온 값을 새로운 위치에 넣어줍니다.

 

위의 두 경우 외에 만약 아무 값도 들어가지 않은 0인 상태인 경우 해당 위치에 값을 넣어줍니다. 방향에 따라 idx 변수의 초기값과 증가 방향이 다를 뿐 비슷한 기조로 구현했습니다.

 

이렇게 구현한 moveBoard 함수를 이용해 DFS 방식으로 4가지의 방향에 대해 발생 가능한 모든 경우에 대해 순회하면서, 5번까지 이동했을 때 현재 board 안에 있는 최댓값을 찾는 getMaxBoard 함수를 이용해 문제에서 요구하는 최댓값을 갱신하는 방식으로 문제 요구사항을 충족시키려 했습니다.

 

---

제출한 소스 코드 (C++)

#include <iostream>
#include <queue>

#define MAX 21

using namespace std;

int n;
int board[MAX][MAX];
int move_board[MAX][MAX];
int max_res = 0;

void moveBoard(int dir) {
	// 0: 왼, 1: 위, 2: 오, 3: 아
	queue<int> q;
	if (dir == 0) {
		for (int i = 1; i <= n; i++) {
			int idx = 1;
			for (int j = 1; j <= n; j++) {
				if(board[i][j] != 0)
					q.push(board[i][j]);
				board[i][j] = 0;
			}

			while (!q.empty()) {
				int x = q.front();
				q.pop();

				// queue에서 하나씩 뽑아서 같으면 더하고 0이면 놓고 떠난다.
				// 이미 차있고 다른 숫자인 경우 다음 칸으로 이동
				if (board[i][idx] == 0) {
					board[i][idx] = x;
				}
				else if (board[i][idx] == x) {
					board[i][idx++] += x;
				}
				else {
					board[i][++idx] = x;
				}
			}
		}
	}
	else if (dir == 1) {
		for (int i = 1; i <= n; i++) {
			int idx = 1;
			for (int j = 1; j <= n; j++) {
				if (board[j][i] != 0)
					q.push(board[j][i]);
				board[j][i] = 0;
			}

			while (!q.empty()) {
				int x = q.front();
				q.pop();

				// queue에서 하나씩 뽑아서 같으면 더하고 0이면 놓고 떠난다.
				// 이미 차있고 다른 숫자인 경우 다음 칸으로 이동
				if (board[idx][i] == 0) {
					board[idx][i] = x;
				}
				else if (board[idx][i] == x) {
					board[idx++][i] += x;
				}
				else {
					// 다른 숫자는 새로운 칸에 쌓는다.
					board[++idx][i] = x;
				}
			}
		}
	}
	else if (dir == 2) {
		for (int i = 1; i <= n; i++) {
			int idx = n;
			for (int j = n; j >= 1; j--) {
				if (board[i][j] != 0)
					q.push(board[i][j]);
				board[i][j] = 0;
			}

			while (!q.empty()) {
				int x = q.front();
				q.pop();

				// queue에서 하나씩 뽑아서 같으면 더하고 0이면 놓고 떠난다.
				// 이미 차있고 다른 숫자인 경우 다음 칸으로 이동
				if (board[i][idx] == 0) {
					board[i][idx] = x;
				}
				else if (board[i][idx] == x) {
					board[i][idx--] += x;
				}
				else {
					board[i][--idx] = x;
				}
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			int idx = n;
			for (int j = n; j >= 1; j--) {
				if (board[j][i] != 0)
					q.push(board[j][i]);
				board[j][i] = 0;
			}

			while (!q.empty()) {
				int x = q.front();
				q.pop();

				// queue에서 하나씩 뽑아서 같으면 더하고 0이면 놓고 떠난다.
				// 이미 차있고 다른 숫자인 경우 다음 칸으로 이동
				if (board[idx][i] == 0) {
					board[idx][i] = x;
				}
				else if (board[idx][i] == x) {
					board[idx--][i] += x;
				}
				else {
					board[--idx][i] = x;
				}
			}
		}
	}

	return;
}

int getMaxBoard() {
	int res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			res = (res > board[i][j]) ? res : board[i][j];
		}
	}
	return res;
}

void DFS(int cnt) {
	if (cnt == 5) {
		int max_num = getMaxBoard();
		max_res = (max_res > max_num) ? max_res : max_num;

		return;
	}
	int copy_board[MAX][MAX];

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			copy_board[i][j] = board[i][j];
		}
	}

	for (int i = 0; i < 4; i++) {
		moveBoard(i);
		DFS(cnt + 1);
		// 원상복구 시켜서 다른 방향으로 실행
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				board[i][j] = copy_board[i][j];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> board[i][j];
		}
	}

	DFS(0);

	cout << max_res;
	
	return 0;
}