[C++][BOJ] 삼성 SW 역량 테스트 기출 문제 - 12100번 2048 (Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

굉장히 복잡한 문제처럼 보이지만 N이 20이 max이고 5번 이동만 하면 되기 때문에 완전탐색 기법을 사용하여 다 해보면 된다.

map을 매번 저장해주고 [왼쪽,오른쪽,위,아래] 로 블록을 밀어주고 그 블록을 그대로 또 한번 [왼쪽,오른쪽,위,아래] 방향으로 밀어주면서 이렇게 5번을 해주고 5번이 됐을 때 블록의 최대 값을 return해주면 모든 case를 다 돌려 볼 수 있다.

 

  1           2          3           4          5

왼쪽 -> 왼쪽 -> 왼쪽 -> 왼쪽 -> 왼쪽 => max값

왼쪽 -> 왼쪽 -> 왼쪽 -> 왼쪽 -> 오른쪽 => max값

왼쪽 -> 왼쪽 -> 왼쪽 -> 왼쪽 -> 위 => max값

왼쪽 -> 왼쪽 -> 왼쪽 -> 왼쪽 -> 아래 => max값

  

이런식으로 쭈욱 완전 탐색을 하는 것이다. 저렇게 위의 숫자를 count로 하여 계속해서 max값을 return해주면 정답이 나온다.

 

재귀에 대해 이해를 반드시 해야 풀 수 있는 문제이다.

 

또한 queue를 통해 2 2 2 가 있으면 2 2 2 를 넣고 앞에서 부터 2, 2 / 2 를 찾아 4 2 를 만들어 준다. 

위로 민다고 치면 2 4 8인데 여기서 합칠 수 있는게 없으므로 2 4 8을 그대로 block에 저장해야 한다.

 

이제 코드를 보자.

 

#include <iostream>
#include <queue>
using namespace std;
#define MAX_MAP 21
 
int map[MAX_MAP][MAX_MAP];
int N;
 
void shift(int block[MAX_MAP][MAX_MAP], int pos)
{
	queue<int> q;
	switch (pos)
	{
	//왼쪽
	case 0:
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
            	//0이 아닌 경우에만 밀면 됨으로 0이 아닌 경우만 queue에 저장
				if (block[i][j])
					q.push(block[i][j]);
                //queue에 넣었으니 0으로 초기화
				block[i][j] = 0;
			}
			int pos = 0;
			//q가 비어질 때 까지 
			while (!q.empty())
			{
				int data = q.front();
				q.pop();
				//현재 block의 위치가 0이면 값을 넣어줌 (처음 case)
				if (block[i][pos] == 0)
				{
					block[i][pos] = data;
				}
                //현재 block의 위치와 data가 같으면 동일한 숫자가 있는 것으로 *2 해줌 (2 / 2 case)
				else if (block[i][pos] == data)
				{
					block[i][pos] = block[i][pos] * 2;
					pos++;
				}
                //다른 값이 있으면 block의 다음 위치에 (2 / 4 case)
				else
				{
					pos++;
					block[i][pos] = data;
				}
			}
		}
		break;
    //오른쪽
	case 1:
		for (int i = 0; i < N; i++)
		{
        	//뒤부터 -> 오른쪽으로 미는 것이기 때문에
			for (int j = N - 1; j >= 0; j--)
			{
				if (block[i][j])
					q.push(block[i][j]);
				block[i][j] = 0;
			}
            //뒤부터 집어 넣기
			int pos = N - 1;
 
			while (!q.empty())
			{
				int data = q.front();
				q.pop();
				if (block[i][pos] == 0)
				{
					block[i][pos] = data;
				}
				else if (block[i][pos] == data)
				{
					block[i][pos] = block[i][pos] * 2;
					pos--;
				}
				else
				{
					pos--;
					block[i][pos] = data;
				}
			}
		}
		break;
	//위
	case 2:
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
            	//i, j 반대로
				if (block[j][i])
					q.push(block[j][i]);
				block[j][i] = 0;
			}
			int pos = 0;
 
			while (!q.empty())
			{
				int data = q.front();
				q.pop();
				if (block[pos][i] == 0)
				{
					block[pos][i] = data;
				}
				else if (block[pos][i] == data)
				{
					block[pos][i] = block[pos][i] * 2;
					pos++;
				}
				else
				{
					pos++;
					block[pos][i] = data;
				}
			}
		}
		break;
	//아래 
	case 3:
		for (int i = 0; i < N; i++)
		{
			for (int j = N - 1; j >= 0; j--)
			{
            	//i, j 반대로
				if (block[j][i])
					q.push(block[j][i]);
				block[j][i] = 0;
			}
			int pos = N - 1;
 
			while (!q.empty())
			{
				int data = q.front();
				q.pop();
				if (block[pos][i] == 0)
				{
					block[pos][i] = data;
				}
				else if (block[pos][i] == data)
				{
					block[pos][i] = block[pos][i] * 2;
					pos--;
				}
				else
				{
					pos--;
					block[pos][i] = data;
				}
			}
		}
		break;
	}
}
int solve(int block[MAX_MAP][MAX_MAP], int count)
{
	int maxVal = -1;
 
	if (count == 5)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (block[i][j] > maxVal) maxVal = block[i][j];
			}
		}
		return maxVal;
	}
 
	//현재 Block을 저장해 놓을 Block선언
	int copyBlock[MAX_MAP][MAX_MAP] = { 0, };
 
	//네 방향
	for (int i = 0; i < 4; i++)
	{
		//Block copy
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				copyBlock[i][j] = block[i][j];
			}
		}
        //Block이동
		shift(copyBlock, i);
        //다음 count로 넘어감
		maxVal = max(maxVal,solve(copyBlock, count + 1));
	}
	return maxVal;
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> map[i][j];
		}
	}
	cout << solve(map, 0) << endl;
}