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

문제

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

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

<그림 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번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;
int max_block;

void get_max(vector< vector<int> > &board)
{
	int i, j;

	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			max_block = max(max_block, board[i][j]);
		}
	}
}

vector< vector<int> > move_up(vector< vector<int> > &board)
{
	vector< vector<int> > res;
	queue<int> q;
	int r, c, idx, block;

	res.resize(N + 1, vector<int> (N + 1, 0));
	for (c = 1; c <= N; c++)
	{
		for (r = 1; r <= N; r++)
		{
			if (board[r][c])
				q.push(board[r][c]);
		}
		idx = 1;
		while (!q.empty())
		{
			block = q.front();
			q.pop();
			if (res[idx][c] == 0)
				res[idx][c] = block;
			else if (res[idx][c] == block)
				res[idx++][c] += block;
			else
				res[++idx][c] = block;
		}
	}
	return res;
}

vector< vector<int> > move_down(vector< vector<int> > &board)
{
	vector< vector<int> > res;
	queue<int> q;
	int r, c, idx, block;

	res.resize(N + 1, vector<int> (N + 1, 0));
	for (c = 1; c <= N; c++)
	{
		for (r = N; r >= 1; r--)
		{
			if (board[r][c])
				q.push(board[r][c]);
		}
		idx = N;
		while (!q.empty())
		{
			block = q.front();
			q.pop();
			if (res[idx][c] == 0)
				res[idx][c] = block;
			else if (res[idx][c] == block)
				res[idx--][c] += block;
			else
				res[--idx][c] = block;
		}
	}
	return res;
}

vector< vector<int> > move_left(vector< vector<int> > &board)
{
	vector< vector<int> > res;
	queue<int> q;
	int r, c, idx, block;

	res.resize(N + 1, vector<int> (N + 1, 0));
	for (r = 1; r <= N; r++)
	{
		for (c = 1; c <= N; c++)
		{
			if (board[r][c])
				q.push(board[r][c]);
		}
		idx = 1;
		while (!q.empty())
		{
			block = q.front();
			q.pop();
			if (res[r][idx] == 0)
				res[r][idx] = block;
			else if (res[r][idx] == block)
				res[r][idx++] += block;
			else
				res[r][++idx] = block;
		}
	}
	return res;
}

vector< vector<int> > move_right(vector< vector<int> > &board)
{
	vector< vector<int> > res;
	queue<int> q;
	int r, c, idx, block;

	res.resize(N + 1, vector<int> (N + 1, 0));
	for (r = 1; r <= N; r++)
	{
		for (c = N; c >= 1; c--)
		{
			if (board[r][c])
				q.push(board[r][c]);
		}
		idx = N;
		while (!q.empty())
		{
			block = q.front();
			q.pop();
			if (res[r][idx] == 0)
				res[r][idx] = block;
			else if (res[r][idx] == block)
				res[r][idx--] += block;
			else
				res[r][--idx] = block;
		}
	}
	return res;
}

void dfs(int depth, vector< vector<int> > board)
{
	if (depth == 5)
	{
		get_max(board);
		return;
	}
	dfs(depth + 1, move_up(board));
	dfs(depth + 1, move_down(board));
	dfs(depth + 1, move_left(board));
	dfs(depth + 1, move_right(board));
}

int main()
{
	int i, j;
	vector< vector<int> > board;

	cin >> N;
	board.resize(N + 1, vector<int> (N + 1, 0));
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			cin >> board[i][j];
		}
	}
	dfs(0, board);
	cout << max_block << endl;
	return 0;
}

 

먼저 벡터에 보드의 초기 상태를 저장한다. dfs를 사용해 5번 이동시키는 모든 경우를 확인하여 가장 큰 블록을 저장한 max_block을 출력한다.

dfs에서는 5번 모두 이동했다면 get_max() 함수를 통해 현재 보드에서 가장 큰 블록을 찾아 max_block을 갱신한 후 리턴한다. 아니라면 모든 방향에 대해 이동하는 경우를 확인한다. move 계열 함수들은 현재 보드를 전달받아 해당하는 방향으로 이동한 후 보드의 상태를 리턴한다. 리턴값은 다음 dfs를 위한 전달 인자로 사용된다.

이동하는 방법은 모든 방향에 대해 동일한 로직을 갖는다. 이동하는 방향에 대해 수평인 라인 단위로 확인한다. 이동하려는 쪽의 값부터 큐에 삽입한다. 이때 0은 빈칸이므로 삽입하지 않는다. 큐가 완성됐으면 새로운 보드에 이동하려는 쪽부터 차례대로 값을 저장한다. 이때 저장된 값들 사이에는 빈칸이 없어야 한다. 만약 해당 위치가 비어있다면 바로 값을 저장한다. 이미 값이 존재하는 경우 저장하려는 값과 같은 값이면 두 값을 합쳐주고, 다른 값이면 다음 위치에 저장한다. 한 번에 두 개 이상의 값은 합쳐질 수 없다. 따라서 값을 합쳐준 경우 바로 다음 위치로 이동해야 한다. 이 로직을 각 방향에 대해 큐에 값을 저장하는 순서와 새로운 보드에 값을 저장하는 순서만 바꾸어 적용하면 된다. 

 

링크

12100번: 2048 (Easy)

inbdni/Baekjoon