Baekjoon 12100 2048 (Easy)

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

소스결과 1988 KB / 0ms

출처 Baekjoon

언어 C++ 17

분류 브루트 포스

 

설명

과거 유행했던 2048 게임을 모방한 Easy버전의 2048게임을 구현하자.

 

2048 게임을 해봤다면 문제 내용은 쉽게 이해 할 수 있는 문제. 단 새로운 블록이 추가 되지 않고. 결과값으로는 만들 수 있는 최대값을 출력 해야 한다.

최대 5번 이동을 한다는 제약, 그리고 움직일 수 있는 방향은 동, 서, 남, 북 4가지 방향이 조건이다.

4가지 방향으로 5번. 4 ^ 5 = 1024 충분히 해 볼만한 경우의 수

 

주의 할 점은 매 회마다 배열을 복사해서 넘겨 주어야 한다.

값을 이동 시킬 때는 현재 넣어야 할 위치를 지정하고, 다음 이동할 블럭을 찾아 이동시키고, 합쳐지는지 합쳐지지 않는지 판별한다.

소스코드는 세로와 가로 방향을 슬라이딩 하는 함수 2개로 나누고, 시작 위치를 기준으로 1을 더해나갈지 빼나갈지를 결정한다.

소스코드는 상당히 직관적이지 않다. 그냥 코드 길이를 조금 줄이고 싶었을뿐.. 가독성은 떨어진다.

 

알고리즘

1. 최초 Board상태를 받는다.

2. 현재 위치를 기준으로 동, 서, 남, 북으로 이동 시키고 이동 결과를 매개변수로 담고 이동 횟수를 1 추가하여 넘긴다.

3. 이동 횟수가 5가 되면 Board에서 가장 큰 값을 찾아 현재까지 발견된 최대 값과 비교하여 갱신한다.

4. 구해진 최대 값을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const short MAX = 20;
int n, res = 0;

void funcHorizontal(int origin[MAX], int result[MAX], int start)
{
	int pos = start;
	int tar = start;
	int adder = start == 0 ? 1 : -1;

	while (true)
	{
		// Move target Point
		for (; (0 <= tar && tar < n) && origin[tar] == 0; tar += adder);

		if (!(0 <= tar && tar < n))
			break;

		if (result[pos]) {
			if (result[pos] == origin[tar])
			{
				result[pos] *= 2;
				pos += adder;
			}
			else
			{
				pos += adder;
				result[pos] = origin[tar];
			}
		}
		else
			result[pos] = origin[tar];

		tar += adder;
	}
}

void funcVertical(int origin[MAX][MAX], int result[MAX][MAX], int col, int start)
{
	int pos = start;
	int tar = start;
	int adder = start == 0 ? 1 : -1;

	while (true)
	{
		// Move target Point
		for (; (0 <= tar && tar < n) && origin[tar][col] == 0; tar += adder);

		if (!(0 <= tar && tar < n))
			break;

		if (result[pos][col]) {
			if (result[pos][col] == origin[tar][col])
			{
				result[pos][col] *= 2;
				pos += adder;
			}
			else
			{
				pos += adder;
				result[pos][col] = origin[tar][col];
			}
		}
		else
			result[pos][col] = origin[tar][col];

		tar += adder;
	}

}

void solve(int board[MAX][MAX], int cnt)
{
	if (cnt == 5)
	{
		int temp_max = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (temp_max < board[i][j])
					temp_max = board[i][j];

		if (res < temp_max)
			res = temp_max;

		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int next[MAX][MAX] = {};

		for (int j = 0; j < n; j++)
		{
			if (i == 0) // left
				funcHorizontal(board[j], next[j], 0);
			else if (i == 1) // right
				funcHorizontal(board[j], next[j], n - 1);
			else if (i == 2) // top
				funcVertical(board, next, j, 0);
			else // bottom
				funcVertical(board, next, j, n - 1);
		}

		solve(next, cnt + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int board[MAX][MAX] = {};

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

	solve(board, 0);

	cout << res;

	return 0;
}