백준
[백준] 12100번 2048 (Easy)
모닝수박
2020. 7. 16. 01:40
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
블록을 옮기는 방향에 따라 다르게 검사하며
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;
}