[BOJ]백준 12100번: 2048(Easy) 풀이 및 반례

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

12100번: 2048 (Easy)

할만한가?싶다가도 ㅇㅏ닌 악마같은 문제.... 😠

어찌보면 삼성 역량테스트의 표준같은 문제였당

 

나는 두 가지 방법으로 문제를 풀었다

① 일단 역테 기출중에서 많이 쓰는, 모든 경우 완전탐색을 위해 DFS로 방향 경우의 수를 구한 뒤

방향 순서에 따라 5번 이동을 해주고 배열 최댓값을 Result로 갱신

이동 예시

이동할 방향이 정해진 뒤 한꺼번에 이동

하지만 이 풀이는,,,,, 상하좌우 모든 이동을 따로따로 구현해야 해서 코드가 엄청나게 더러워진다는 단점이 있었당 ㅠ

그래서 이동 섹션을 한 번만 구현할 수 없을까.....? 하다가

② 배열 돌리기를 생각해냈다 .....

90도 회전하고 위로 이동한 것 = 오른쪽으로 이동한 것

그림을 보면

원래 상태에서 배열을 90도 회전시킨 다음 위로 이동하면 오른쪽으로 이동한 것과 배열 상태가 같다

는 것을 알 수 있다

물론 배열이 회전되어있긴 하지만 문제에서는 상관없기 때문에 마구 돌려주자

1번 방법에서처럼 방향을 전부 정한 뒤에 이동&회전을 해도 되지만

다음 depth를 호출할 때 마다 이동&회전을 해줘도 된다

 

1️⃣번풀이

#include <cstdio>
#include <stack>
using namespace std;
int n, ans, board[22][22], m[22][22], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, seq[8];
stack<int> s[22];
void move(int arr[][22], int dir) {
	switch (dir) {
	case 0:	//동
		for (int i = 0; i < n; i++)
			for (int j = n - 1, check = 0; j >= 0; j--) {
				if (!arr[i][j])continue;
				if (!s[i].empty() && !check && s[i].top() == arr[i][j]) {
					s[i].pop();
					s[i].push(arr[i][j] * 2);
					check = 1;
				}
				else {
					s[i].push(arr[i][j]);
					check = 0;
				}
				arr[i][j] = 0;
			}
		for (int i = 0; i < n; i++)
			while (!s[i].empty()) {
				arr[i][n - s[i].size()] = s[i].top();
				s[i].pop();
			}
		break;
	case 1:	//남
		for (int i = 0; i < n; i++)
			for (int j = n - 1, check = 0; j >= 0; j--) {
				if (!arr[j][i])continue;
				if (!s[i].empty() && !check && s[i].top() == arr[j][i]) {
					s[i].pop();
					s[i].push(arr[j][i] * 2);
					check = 1;
				}
				else {
					s[i].push(arr[j][i]);
					check = 0;
				}

				arr[j][i] = 0;
			}
		for (int i = 0; i < n; i++)
			while (!s[i].empty()) {
				arr[n - s[i].size()][i] = s[i].top();
				s[i].pop();
			}
		break;
	case 2:	//서
		for (int i = 0; i < n; i++)
			for (int j = 0, check = 0; j < n; j++) {
				if (!arr[i][j])continue;
				if (!s[i].empty() && !check && s[i].top() == arr[i][j]) {
					s[i].pop();
					s[i].push(arr[i][j] * 2);
					check = 1;
				}
				else {
					s[i].push(arr[i][j]);
					check = 0;
				}

				arr[i][j] = 0;
			}
		for (int i = 0; i < n; i++)
			while (!s[i].empty()) {
				arr[i][s[i].size() - 1] = s[i].top();
				s[i].pop();
			}
		break;
	case 3:	//북
		for (int i = 0; i < n; i++)
			for (int j = 0, check = 0; j < n; j++) {
				if (!arr[j][i])continue;
				if (!s[i].empty() && !check && s[i].top() == arr[j][i]) {
					s[i].pop();
					s[i].push(arr[j][i] * 2);
					check = 1;
				}
				else {
					s[i].push(arr[j][i]);
					check = 0;
				}

				arr[j][i] = 0;
			}
		for (int i = 0; i < n; i++)
			while (!s[i].empty()) {
				arr[s[i].size() - 1][i] = s[i].top();
				s[i].pop();
			}
		break;
	}
}
void func(int dep) {
	if (dep == 5) {
		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)
			m[i][j] = board[i][j];
		//복사

		for (int i = 0; i < 5; i++)
			move(m, seq[i]);

		for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)
			if (m[i][j] > ans)ans = m[i][j];
		return;
	}

	for (int i = 0; i < 4; i++) {
		seq[dep] = i;
		func(dep + 1);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &board[i][j]);
	func(0);
	printf("%d", ans);
	return 0;
}

2️⃣번풀이

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int n, ans, board[22][22], m[22][22], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int seq[5], kk[] = { 0,3,0,1,3 };
stack<int> s[22];
void move(int arr[][22]) {
	for (int i = 0; i < n; i++)
		for (int j = 0, check = 0; j < n; j++) {
			if (!arr[j][i])continue;
			if (!s[i].empty() && !check && s[i].top() == arr[j][i]) {
				s[i].pop();
				s[i].push(arr[j][i] * 2);
				check = 1;
			}
			else {
				s[i].push(arr[j][i]);
				check = 0;
			}

			arr[j][i] = 0;
		}
	for (int i = 0; i < n; i++)
		while (!s[i].empty()) {
			arr[s[i].size() - 1][i] = s[i].top();
			s[i].pop();
		}
}
void rotate(int arr[][22]) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			m[j][n - 1 - i] = arr[i][j];
	memcpy(arr, m, sizeof(m));
}
void func(int dep) {
	if (dep == 5) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (board[i][j] > ans)ans = board[i][j];
		return;
	}

	int temp[22][22];
	for (int i = 0; i < 4; i++) {
		memcpy(temp, board, sizeof(board));
		move(board);
		seq[dep] = i;
		func(dep + 1);
		memcpy(board, temp, sizeof(board));
		rotate(board);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &board[i][j]);
	func(0);
	printf("%d", ans);
	return 0;
}

2번 풀이 코드가 1번 풀이 코드의 절반 길이다 ^^

각 경우의 수는 4^5 = 1024번이고 각각의 경우에 대해 4번씩 회전(시간복잡도 O(n^2)) * 이동(시간복잡도 O(n^2))

굉장히 복잡하당 ...

 

반례👇👇👇

#1

3

2 2 2

4 4 4

8 8 8 

=>16

 

#2

2

8 16

16 8

=>16

 

#3

4

8 16 0 0

0 0 16 8

0 0 0 0

0 0 0 0

=>32

 

4
0 0 0 0
4 0 0 0
8 32 4 0
8 8 4 0
->64

 

10
8 8 4 16 32 0 0 8 8 8
8 8 4 0 0 8 0 0 0 0
16 0 0 16 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 16
0 0 0 0 0 0 0 0 0 2
->128

 

10
16 16 8 32 32 0 0 8 8 8
16 0 0 0 0 8 0 0 0 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
->64

 

10
0 0 0 0 0 32 8 64 8 16
0 0 0 0 0 0 0 16 8 16
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
->128