[백준] 12100번 2048 (Easy)

12100번: 2048 (Easy)

블록을 옮기는 방향에 따라 다르게 검사하며

 

1. 위로 옮길 때 -> 각 열 위에서부터 검사

2. 아래로 옮길 때 -> 각 열 아래에서부터 검사

3. 왼쪽으로 옮길 때 -> 각 행 왼쪽에서부터 검사

4. 오른쪽으로 옮길 때 -> 각 행 오른쪽에서부터 검사

 

같은 숫자가 연속해서 나오면 (빈칸 무시)

그 두 숫자를 더한 값을 큐에 넣고

같은 숫자가 연속하지 않을 때는

그 숫자만 큐에 넣는다.

 

한 줄의 검사가 끝나면

큐에 있는 숫자를 보드판에 경우에 맞게 저장한다.

 

1번의 경우 -> 위에서부터 저장, 큐가 비면 0 저장

2번의 경우 -> 아래에서부터 저장, 큐가 비면 0 저장

3번의 경우 -> 왼쪽에서부터 저장, 큐가 비면 0 저장

4번의 경우 -> 오른쪽에서부터 저장, 큐가 비면 0 저장

 

이렇게 블록의 이동을 끝내면 재귀 호출을 이용한 DFS로 다음 이동을 해준다.

이때 이동 횟수가 5가 되면 그때 얻을 수 있는 가장 큰 블록의 값을 갱신해준다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int N, Max = 2, tmp = -1;
int board[21][21];
queue <int> q;
void Game(int cnt) {
	if (cnt == 5) {
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (board[i][j] > Max) Max = board[i][j];
		return;
	}
	for (int k = 0; k < 4; k++) {
		int board2[21][21] = { 0 };
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) board2[i][j] = board[i][j];
		switch (k)
		{
		case 0: //위쪽
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (tmp == -1 && board[j][i] != 0) tmp = board[j][i];
					else if (tmp != -1 && board[j][i] != tmp && board[j][i] != 0) {
						q.push(tmp);
						if (!board[j][i]) tmp = -1;
						else tmp = board[j][i];
					}
					else if (board[j][i] == tmp) {
						q.push(tmp * 2);
						tmp = -1;
					}
				}
				if (tmp != -1) q.push(tmp);
				for (int j = 0; j < N; j++) {
					if (!q.empty()) board[j][i] = q.front(), q.pop();
					else board[j][i] = 0;
				}
				tmp = -1;
			}
			break;
		case 1: //아래쪽
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (tmp == -1 && board[j][i] != 0) tmp = board[j][i];
					else if (tmp != -1 && board[j][i] != tmp && board[j][i] != 0) {
						q.push(tmp);
						if (!board[j][i]) tmp = -1;
						else tmp = board[j][i];
					}
					else if (board[j][i] == tmp) {
						q.push(tmp * 2);
						tmp = -1;
					}
				}
				if (tmp != -1) q.push(tmp);
				for (int j = N - 1; j >= 0; j--) {
					if (!q.empty()) board[j][i] = q.front(), q.pop();
					else board[j][i] = 0;
				}
				tmp = -1;
			}
			break;
		case 2: //왼쪽
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (tmp == -1 && board[i][j] != 0) {
						tmp = board[i][j];
					}
					else if (tmp != -1 && board[i][j] != tmp && board[i][j] != 0) {
						q.push(tmp);
						if (!board[i][j]) tmp = -1;
						else tmp = board[i][j];
					}
					else if (board[i][j] == tmp) {
						q.push(tmp * 2);
						tmp = -1;
					}
				}
				if (tmp != -1) q.push(tmp);
				for (int j = 0; j < N; j++) {
					if (!q.empty()) board[i][j] = q.front(), q.pop();
					else board[i][j] = 0;
				}
				tmp = -1;
			}
			break;
		case 3: //오른쪽
			for (int i = 0; i < N; i++) {
				for (int j = N - 1; j >= 0; j--) {
					if (tmp == -1 && board[i][j] != 0) {
						tmp = board[i][j];
					}
					else if (tmp != -1 && board[i][j] != tmp && board[i][j] != 0) {
						q.push(tmp);
						if (!board[i][j]) tmp = -1;
						else tmp = board[i][j];
					}
					else if (board[i][j] == tmp) {
						q.push(tmp * 2);
						tmp = -1;
					}
				}
				if (tmp != -1) q.push(tmp);
				for (int j = N - 1; j >= 0; j--) {
					if (!q.empty()) board[i][j] = q.front(), q.pop();
					else board[i][j] = 0;
				}
				tmp = -1;
			}
			break;
		}
		Game(cnt + 1);
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) board[i][j] = board2[i][j];
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> board[i][j];
	Game(0);
	cout << Max;
	return 0;
}