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

# 문제링크

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

잘 푼 것 같은데 채점에서 광탈하길래 우울했던 문제.. 원인은 freopen() 을 지워주지 않아서였다 ㅠㅠㅠㅠㅠㅠ

그것도 모르고 왜 틀렸는지 몇 시간 더 뜯어보면서 스트레스 받았다..

 

문제를 처음 읽고, "최대 5번" 이동시켜서 얻을 수 있는 가장 큰 수를 구하는 것이기 때문에, 모든 경우의 수를 다 구해봐도 괜찮겠다고 생각했다. (배열의 크기도 20*20 밖에 되지 않는다.) 바로, DFS로 모든 이동 방법을 구한다음에 움직여 봐야지! 이렇게 생각했다. 

 

// 모든 경우의 수 구하기
void DFS(int node) {
	if (node == 5) {
		Move();
		int ret = FindMax();
		if (ret > ans) ans = ret;
		return;
	}

	for (int i = 0; i < 4; i++) { // 4가지 방향 
		dir[node] = i;
		DFS(node + 1);
	}
}

 

움직일 때는 map을 tmp 에 복사해서 시뮬레이션을 돌려보았다. 움직이는 거는, 1) 같은 숫자 두 개를 더해주는 것, 2) 밀어주기 이렇게 진행했다. 

 

두 개를 합쳐주면 배열 중간에 빈 공간이 생긴다. 문제의 예시를 오른쪽으로 민다고 가정하고 같은 숫자 두개를 합쳐주면 아래와 같이 빈 공간이 생긴다. 

 

2 2 2           2 0 4

4 4 4    ->    4 0 8 

8 8 8           8 0 16 

 

그러면 이걸 오른쪽으로 한 번 더 밀어줘야 한다. 그렇게 두 번 진행해주면 된다. 밀어주는 게 복잡하게 느껴졌는데, queue활용하여 해결했다. for 문을 돌면서 0이 아니면 queue.에 넣어주고, 다시 queue에 밀어주는 방향부터 차곡차곡 넣어주면 밀어줄 수 있다.

 

// 밀기 
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
			if (tmp[j][i] == 0)continue;
			q.push(tmp[j][i]);
			tmp[j][i] = 0;
	}
	int n = q.size();
	for (int j = 0; j < n; j++) {
		tmp[j][i] = q.front(); q.pop();
	}
}

 

 

 

# 제출 코드

 

#include <cstdio>
#include <queue>
using namespace std;
// 2048

int map[21][21];
int tmp[21][21];
int N;
int ans;
int dir[5];
queue <int> q;

void Copy() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			tmp[i][j] = map[i][j];
		}
	}
}
int FindMax() {
	int max = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (tmp[i][j] > ans) ans = tmp[i][j];
		}
	}
	return max;
}
void Move() {
	Copy(); // map 을 tmp 에 복사해서 사용

	for (int d = 0; d < 5; d++) { // 5번 이동
		switch (dir[d]) {
		case 0: // 위로 밀기 
			// 합치기
			for (int i = 0; i < N; i++) {
				int* s = 0;
				for (int j = 0; j < N ; j++) {
					if (tmp[j][i] == 0)continue;
					if (s == 0) { s = &tmp[j][i]; continue; }
					if (*s == tmp[j][i]) {
						*s *= 2;
						s = 0;
						tmp[j][i] = 0;
					}
					else {
						s = &tmp[j][i];
					}
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (tmp[j][i] == 0)continue;
					q.push(tmp[j][i]);
					tmp[j][i] = 0;
				}
				int n = q.size();
				for (int j = 0; j < n; j++) {
					tmp[j][i] = q.front(); q.pop();
				}
			}
			break;
		case 1: // 아래로 밀기 
				// 합치기
			for (int i = 0; i < N; i++) {
				int* s = 0;
				for (int j = N-1; j >= 0; j--) {
					if (tmp[j][i] == 0)continue;
					if (s == 0) { s = &tmp[j][i]; continue; }
					if (*s == tmp[j][i]) {
						*s *= 2;
						s = 0;
						tmp[j][i] = 0;
					}
					else {
						s = &tmp[j][i];
					}
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = N-1; j >= 0; j--) {
					if (tmp[j][i] == 0)continue;
					q.push(tmp[j][i]);
					tmp[j][i] = 0;
				}
				int n = q.size();
				for (int j = N-1; j > N -1 - n; j--) {
					tmp[j][i] = q.front(); q.pop();
				}
			}
			break;
		case 2: // 왼쪽 
			for (int i = 0; i < N; i++) {
				int* s = 0;
				for (int j = 0; j < N; j++) {
					if (tmp[i][j] == 0)continue;
					if (s == 0) { s = &tmp[i][j]; continue; }
					if (*s == tmp[i][j]) {
						*s *= 2;
						s = 0;
						tmp[i][j] = 0;
					}
					else {
						s = &tmp[i][j];
					}
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (tmp[i][j] == 0)continue;
					q.push(tmp[i][j]);
					tmp[i][j] = 0;
				}
				int n = q.size();
				for (int j = 0; j < n; j++) {
					tmp[i][j] = q.front(); q.pop();
				}
			}
			break;
		case 3: // 오른쪽 
			for (int i = 0; i < N; i++) {
				int* s = 0;
				for (int j = N - 1; j >= 0; j--) {
					if (tmp[i][j] == 0)continue;
					if (s == 0) { s = &tmp[i][j]; continue; }
					if (*s == tmp[i][j]) {
						*s *= 2;
						s = 0;
						tmp[i][j] = 0;
					}
					else {
						s = &tmp[i][j];
					}
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (tmp[i][j]  == 0)continue;
					q.push(tmp[i][j]);
					tmp[i][j] = 0;
				}
				int n = q.size();
				for (int j = N - 1; j > N - 1 - n; j--) {
					tmp[i][j] = q.front(); q.pop();
				}
			}
			break;
		}
	}
}
void DFS(int node) {
	if (node == 5) {
		Move();
		int ret = FindMax();
		if (ret > ans) ans = ret;
		return;
	}

	for (int i = 0; i < 4; i++) { // 4가지 방향 
		dir[node] = i;
		DFS(node + 1);
	}
}
void Input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}
int main() {
	Input();
	DFS(0);
	printf("%d\n", ans);
	return 0;
}

 

# p. s freopen()의 흔적들...