[코드트리] 2048 게임 (삼성 SW 역량테스트 2016 하반기 2번 문제)

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/2048-game

이후 설명 및 입/출력은 링크 참고

 

2048 게임 문제 풀이는 BOJ 12100 : 2048 Easy와 같다.

#include <stdio.h>

#define MAX (20 + 5)

#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)

int T;
int N;
int MAP[MAX][MAX];
int ANSWER;

void(*pMove[5])(int map[][MAX]);

void input()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			scanf("%d", &MAP[r][c]);
}

void output(int map[][MAX])
{
	for (int i = 0; i < N; i++)
	{
		for (int k = 0; k < N; k++)
			printf("%d ", map[i][k]);
		putchar('\n');
	}
}

int findMax(int map[][MAX])
{
	int max = 0;
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			if (max < map[r][c]) max = map[r][c];

	return max;
}

void initMap(int map[][MAX])
{
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			map[r][c] = 0;
}

void mapCopy(int dest[][MAX], int src[][MAX])
{
	for (int r = 0; r < N; r++)
		for (int c = 0; c < N; c++)
			dest[r][c] = src[r][c];
}

void moveLeft(int map[][MAX])
{
	int tmp[MAX][MAX] = { 0 };

	initMap(tmp);

	for (int r = 0; r < N; r++)
	{
		int step = 0;
		for (int c = 0; c < N; c++)
		{
			if (map[r][c] == 0) continue;

			tmp[r][step++] = map[r][c];
		}

		for (int c = 0; c < N - 1; c++)
		{
			if (tmp[r][c] != tmp[r][c + 1]) continue;
			else
			{
				tmp[r][c] *= 2;

				for (int cc = c + 1; cc < N - 1; cc++) tmp[r][cc] = tmp[r][cc + 1];
				tmp[r][N - 1] = 0;
			}
		}
	}

	mapCopy(map, tmp);
}

void moveUp(int map[][MAX])
{
	int tmp[MAX][MAX] = { 0 };

	initMap(tmp);

	for (int c = 0; c < N; c++)
	{
		int step = 0;
		for (int r = 0; r < N; r++)
		{
			if (map[r][c] == 0) continue;

			tmp[step++][c] = map[r][c];
		}

		for (int r = 0; r < N - 1; r++)
		{
			if (tmp[r][c] != tmp[r + 1][c]) continue;
			else
			{
				tmp[r][c] *= 2;

				for (int rr = r + 1; rr < N - 1; rr++) tmp[rr][c] = tmp[rr + 1][c];
				tmp[N - 1][c] = 0;
			}
		}
	}

	mapCopy(map, tmp);
}

void moveRight(int map[][MAX])
{
	int tmp[MAX][MAX] = { 0 };

	initMap(tmp);

	for (int r = 0; r < N; r++)
	{
		int step = N - 1;
		for (int c = N - 1; c >= 0; c--)
		{
			if (map[r][c] == 0) continue;

			tmp[r][step--] = map[r][c];
		}

		for (int c = N - 1; c >= 0; c--)
		{
			if (tmp[r][c] != tmp[r][c - 1]) continue;
			else
			{
				tmp[r][c] *= 2;

				for (int cc = c - 1; cc >= 0; cc--) tmp[r][cc] = tmp[r][cc - 1];
				tmp[r][0] = 0;
			}
		}
	}

	mapCopy(map, tmp);
}

void moveDown(int map[][MAX])
{
	int tmp[MAX][MAX] = { 0 };

	initMap(tmp);

	for (int c = 0; c < N; c++)
	{
		int step = N - 1;
		for (int r = N - 1; r >= 0; r--)
		{
			if (map[r][c] == 0) continue;

			tmp[step--][c] = map[r][c];
		}

		for (int r = N - 1; r >= 0; r--)
		{
			if (tmp[r][c] != tmp[r - 1][c]) continue;
			else
			{
				tmp[r][c] *= 2;

				for (int rr = r - 1; rr >= 0; rr--) tmp[rr][c] = tmp[rr - 1][c];
				tmp[0][c] = 0;
			}
		}
	}

	mapCopy(map, tmp);
}


void DFS(int L, int map[][MAX])
{
	if (L > 5)
	{
		int maxBlock = findMax(map);
		if (ANSWER < maxBlock) ANSWER = maxBlock;

		return;
	}

	int copy[MAX][MAX] = { 0 };

	initMap(copy);

	for (int i = 0; i < 4; i++)
	{
		mapCopy(copy, map);

		pMove[i](copy);

		DFS(L + 1, copy);
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();
		ANSWER = 0;

		pMove[LEFT] = moveLeft;
		pMove[UP] = moveUp;
		pMove[RIGHT] = moveRight;
		pMove[DOWN] = moveDown;

		DFS(1, MAP);

		printf("%d\n", ANSWER);
	}

	return 0;
}