20. SW_Test 연습 백준 12100번 2048 (Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

 

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

두개의 큐를 이용하여 푸는 문제. 

큐 자료구조의 개념을 확실히 안다면 풀수있다.

 

#pragma warning (disable : 4996)
#include <iostream>
#include <cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
int tmpMap[20][20];
int ans = 0;
queue <int > q;
queue <int> tmpq;
bool cursh = false;
void update(int y, int x) {
	if (!tmpq.empty()) {
		tmpMap[y][x] = tmpq.front();
		tmpq.pop();
	}
	else {
		tmpMap[y][x] = 0;
	}
}
void merge() {
	if (!q.empty()) {
		while (!q.empty()) {
			int cunTmp = q.front();
			q.pop();
			if (!q.empty()) {
				int nexttmp = q.front();
				if (cunTmp == nexttmp) {
					tmpq.push(nexttmp * 2);
					q.pop();
				}
				else {
					tmpq.push(cunTmp);
				}

			}
			else {
				tmpq.push(cunTmp);
			}
		}
	}
}
void move(int cnt, int dir) {
	if (cnt == 6) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ans = max(ans, tmpMap[i][j]);

			}
		}
	}
	else {
		int Map[20][20];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				Map[i][j] = tmpMap[i][j];
			}
		}

		if (dir == 1) {
			for (int j = 0; j < N; j++) {
				for (int i = 0; i < N; i++) {
					if (tmpMap[i][j] != 0) {
						q.push(tmpMap[i][j]);
					}
				}
				merge();
				for (int i = 0; i < N; i++) {
					update(i, j);
				}
			}
		}
		else if (dir == 2) {
			for (int j = 0; j < N; j++) {
				for (int i = N - 1; i >= 0; i--) {
					if (tmpMap[i][j] != 0) {
						q.push(tmpMap[i][j]);
					}
				}
				merge();
				for (int i = N - 1; i >= 0; i--) {
					update(i, j);
				}
			}
		}
		else if (dir == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (tmpMap[i][j] != 0) {
						q.push(tmpMap[i][j]);
					}
				}
				merge();
				for (int j = 0; j < N; j++) {
					update(i, j);
				}
			}
		}
		else if (dir == 4) {
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (tmpMap[i][j] != 0) {
						q.push(tmpMap[i][j]);
					}
				}
				merge();
				for (int j = N - 1; j >= 0; j--) {
					update(i, j);
				}
			}
		}
		for (int D = 1; D <= 4;D++) {
			move(cnt + 1, D);
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				tmpMap[i][j] = Map[i][j];
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &tmpMap[i][j]);
		}
	}
	move(0, 0);
	printf("%d", ans);
	return 0;
}