문제
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 1) 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 2) 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 3) 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.
<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.
<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.
4) 마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
구현해야할 조건
한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이며, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 됩니다. 한 번의 이동에서 이미 합쳐진 블록은 다른 블록과 다시 합쳐질 수 없다라는 점을 유의 해야 합니다. 이미 합쳐지게 된 블록은 값이 들어와도 합쳐질수 없다라는 점!
똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐지는 점도 유의해야 합니다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하세요!
code
#include<iostream>
#include<queue>
#include<vector>
#define MAX 21
#define INF 987654321
using namespace std;
int n;
int board[MAX][MAX];
int res = -INF;
void move(int dir)
{
queue<int> q;
switch(dir)
{
case 0: // up
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(board[j][i])
q.push(board[j][i]);
board[j][i] = 0;
}
int idx = 0;
while(!q.empty())
{
int data = q.front();
q.pop();
if(board[idx][i] == 0) // 보드의 상태가 0이라는 것은 비어있다는 것
board[idx][i] = data; // 그대로 넣어준다.
else if(board[idx][i] == data) // 들어갈 데이터가 똑같다
{
board[idx][i] *= 2; // 2배로 늘려주고
idx++; //board 저장할 곳을 옮겨주면서, 한 번의 이동에서 이미 합쳐진 블록은 다른 블록과 다시 합쳐지지 않는다.
}
else
{
idx++; // 블록 들어갈 위치 변경, 값이 같이 않으면
board[idx][i] = data;
}
}
}
break;
case 1: // down
for(int i = 0; i < n; i++)
{
for(int j = n-1; j >= 0; j--)
{
if(board[j][i])
q.push(board[j][i]);
board[j][i] = 0;
}
int idx = n-1;
while(!q.empty())
{
int data = q.front();
q.pop();
if(board[idx][i] == 0)
board[idx][i] = data;
else if(board[idx][i] == data)
{
board[idx][i] *= 2;
idx--;
}
else
{
idx--;
board[idx][i] = data;
}
}
}
break;
case 2: // left
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(board[i][j])
q.push(board[i][j]);
board[i][j] = 0;
}
int idx = 0;
while(!q.empty())
{
int data = q.front();
q.pop();
if(board[i][idx] == 0)
board[i][idx] = data;
else if(board[i][idx] == data)
{
board[i][idx] *= 2;
idx++;
}
else
{
idx++;
board[i][idx] = data;
}
}
}
break;
case 3: // right
for(int i = 0; i < n; i++)
{
for(int j = n-1; j >= 0; j--)
{
if(board[i][j])
q.push(board[i][j]);
board[i][j] = 0;
}
int idx = n-1;
while(!q.empty())
{
int data = q.front();
q.pop();
if(board[i][idx] == 0)
board[i][idx] = data;
else if(board[i][idx] == data)
{
board[i][idx] *= 2;
idx--;
}
else
{
idx--;
board[i][idx] = data;
}
}
}
break;
}
}
void DFS(int cnt)
{
if(cnt == 5) // 최대 5번 이동해 만들 수 있는 가장 큰 블록
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(res < board[i][j])
res = board[i][j]; // 가장 큰 블록의 값을 구하는 방법
}
}
return;
}
int copyBoard[MAX][MAX]; // DFS를 사용하기 때문에 항상 이전 값을 유지해야 한다.
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
copyBoard[i][j] = board[i][j]; // 이전 값 유지
}
}
for(int i = 0; i < 4; i++)
{
//이동 하고
move(i); // 0 : up, 1 : down, 2: left, 3: right 이
DFS(cnt+1); // 최대 갯수 카운트 해주고
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
board[i][j] = copyBoard[i][j]; // 이동이 되면 저장
}
}
}
return;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> board[i][j]; // 입력이 주어지고
DFS(0); // 최대 5번 이동해서 만들 수 있는 가장 큰 블록을 구하세요.
cout << res;
return 0;
}'PS > Samsung' 카테고리의 다른 글
| [백준/c++] 14500 테트로미노 (0) | 2022.02.03 |
|---|---|
| [백준/c++] 14502 연구소 (0) | 2022.02.03 |
| [백준/c++] 14499 주사위 굴리기 (0) | 2022.02.02 |
| [백준/c++] 3190 뱀 (0) | 2022.02.02 |
| [백준] 13460 구슬탈출 2 (0) | 2022.01.13 |