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

 

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

 

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

12100번: 2048 (Easy)

 

---

 

해결전략

 

구현

재귀적인 깊이 우선 탐색(DFS)

시뮬레이션
그리드 회전

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int n; // nxn 격자 크기
vector<vector<int>> v; // v: 원본 격자
int maxBlock; // 게임판에 존재하는 가장 큰 블록의 값

void Move(vector<vector<int>> &v) // 한 방향(왼쪽)으로 블록을 이동시키고 합치는 함수
{
	for(int y=0; y<n; y++)
	{
		deque<int> dq;
		bool chMerge = false;

		for(int x = 0; x < n; x++) // 한 줄씩 블록을 확인하면서 같은 값의 블록을 합침
		{
			if(v[y][x] != 0) // 0이 아닌 경우만 고려함 (블록이 있는 경우)
			{
				// 이전에 합친적 없고, 현재 블록과 같은 값을 가진 블록이 dq에 있으면
				if(chMerge == false && !dq.empty() && dq.back() == v[y][x])
				{
					dq.pop_back(); // dq에서 마지막 원소를 제거
					dq.push_back(v[y][x] * 2); // 블록 합치기
					chMerge = true; // true로 설정하여 바로 다음 동일한 숫자의 블록이 오더라도 병합되지 않도록 한다.
				}
				else // 블록이 없는 경우
				{
					dq.push_back(v[y][x]); // 현재 위치의 값을 dq에 추가
					chMerge = false;
				}

				v[y][x] = 0; // 해당 위치의 값을 비운다.
			}
		}

		// 이동 및 병합 후 결과를 map에 반영함. 모든 처리가 완료된 후, 남아 있는 값들(dq)을 다시 격자판(v)에 채워 넣습니다.
		int idx = 0;
		while(!dq.empty())
		{
			v[y][idx++] = dq.front();
			dq.pop_front();
		}
	}
}

void Rotate(vector<vector<int>>& arr) // 시계 방향으로 회전하는 함수
{
	vector<vector<int>> temp(n, vector<int>(n)); // temp의 크기를 nxn으로 초기화
	for(int y=0; y<n; y++){
		for (int x = 0; x < n; x++) {
			temp[x][n - 1 - y] = arr[y][x];
		}
	}

	arr = temp;
}

void DFS(int cnt) // 모든 가능한 상태를 탐색하는 함수. cnt는 현재까지 몇 번 움직였는지 카운트.
{
	if (cnt >= 5)
	{
		for(int y=0; y<n; y++){
			for (int x = 0; x < n; x++) {
				if (v[y][x] > maxBlock) maxBlock = v[y][x]; // 최대 블록 값을 갱신
			}
		}
		return;
	}

	vector<vector<int>> tmp(n, vector<int>(n)); // tmp: 임시 저장소로 사용되는 격자
	for(int i=0; i<4; i++) // 4방향 탐색
	{
		tmp = v;
		Move(v); 
		DFS(cnt + 1); // 재귀적으로 다음 상태를 탐색
		v = tmp; // 원상 복구
		Rotate(v); // 회전
	}
}

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

	cin >> n;
	v.resize(n, vector<int>(n));
	for(int y=0; y<n; y++){
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
		}
	}

	DFS(0);

	cout << maxBlock;

	return 0;
}

 

Move 함수:

• 주어진 격자판에 대해 한 방향으로 모든 블록을 이동시키고, 같은 값의 인접한 블록들을 합친다. 이동 및 병합 후 결과를 격자에 반영한다.

 

Rotate 함수: 

• 주어진 격자판을 시계 방향으로 90도 회전시킨다.
• Move 함수가 한쪽으로 미는 함수다. 상하좌우 모두 검사할 수 있도록 회전시키는 것이다. 회전을 4번을 하면 처음 방향이랑 같다.

 

DFS 함수: 

• 깊이 우선 탐색(DFS) 알고리즘을 사용하여 가능한 모든 상태를 탐색하고, 각각에 대해 최대 블록 값을 계산한다.
• v를 temp에 복사해두는 이유는?
  • 하나의 원본 배열을 기준으로 4방향 이동 검사하여야 한다.
  • 만약 temp 없이 4방향으로 돌리면 돌아간 상태에서 또 돈다. 이건 원하는 결과가 아니다.

 

---

 

해설

 

 

 

 

 

 

---