백준 12100 2048 (Easy) C++

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

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

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

<그림 1>	<그림 2>	<그림 3>

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

<그림 4>	<그림 5>	<그림 6>	<그림 7>

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

<그림 8>	<그림 9>

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

<그림 10>	<그림 11>	<그림 12>	<그림 13>

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

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

<그림 14>	<그림 15>

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

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

입력

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

출력

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

 

풀이

그림들이 짤렸는데 백준 링크에 들어가면 볼 수 있다.

2048 게임 해보기

https://play2048.co/

2048

 

키보드 버튼의 방향

void shift(int type): 방향 전환 하는 함수

0→ left

1 → right

2 → up

3 → down

 

void DFS(int cnt): 깊이 탐색으로 최대 5번 블록을 이동시킬 수 있다.

#include <iostream>
#include <queue>

using namespace std;
const int MAX = 20;
int N;
int board[MAX][MAX];
int maxBlock;


void shift(int type){
	queue<int> q;

	//put numbers in queue
	switch (type)
	{
		//left
	case 0:
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (board[i][j]){
					q.push(board[i][j]); //큐에 블록을 넣음
				}
				board[i][j] = 0; //기존 블록은 비어진 상태로 
			}

			int idx = 0;

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

				if (board[i][idx] == 0){
					board[i][idx] = data;
				}
				else if (board[i][idx] == data){
					board[i][idx] *= 2;
					idx++;
				}
				else{
					idx++;
					board[i][idx] = data;
				}
			}
		}
		break;

		//right
	case 1:
		for (int i = 0; i < N; i++){
			for (int j = N - 1; j >= 0; j--){
				if (board[i][j])
					q.push(board[i][j]);
				board[i][j] = 0;
			}

			int idx = N - 1;

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

				if (board[i][idx] == 0){ //비어 있을 때
					board[i][idx] = data;
				}
				else if (board[i][idx] == data){ // data랑 합쳐지려는 board칸의 값과 같을 때
					board[i][idx] *= 2;
					idx--;
				}
				else{  // data랑 합쳐지려는 board칸의 값과 다를 때
					idx--;
					board[i][idx] = data;
				}
			}
		}
		break;

		//up
	case 2:
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (board[j][i]){
					q.push(board[j][i]);
				}
				board[j][i] = 0;
			}

			int idx = 0;

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

				if (board[idx][i] == 0){
					board[idx][i] = data;
				}
				else if (board[idx][i] == data){
					board[idx][i] *= 2;
					idx++;
				}
				else{
					idx++;
					board[idx][i] = data;
				}
			}
		}
		break;

		//down
	case 3:
		for (int i = 0; i < N; i++){
			for (int j = N - 1; j >= 0; j--){
				if (board[j][i]){
					q.push(board[j][i]);
				}
				board[j][i] = 0;
			}

			int idx = N - 1;

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

				if (board[idx][i] == 0){
					board[idx][i] = data;
				}
				else if (board[idx][i] == data){
					board[idx][i] *= 2;
					idx--;
				}
				else{
					idx--;
					board[idx][i] = data;
				}
			}
		}
		break;
	}
}

void DFS(int cnt)
{
	if (cnt == 5){ //5번 이동 완료 
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				maxBlock = max(maxBlock, board[i][j]);
			}
		}
		return;
	}

	int copyBoard[MAX][MAX];
	//save current board
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			copyBoard[i][j] = board[i][j];
		}
	}

	for (int i = 0; i < 4; i++){ //모든 방향 다 카운트해봐야 함.
		shift(i);
		DFS(cnt + 1);

		//recover board state
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				board[i][j] = copyBoard[i][j];
			}
		}
	}
}

int main(void){
	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> board[i][j];
		}
	}

	DFS(0);

	cout << maxBlock << endl;

	return 0;
}