[BOJ/백준 12100/C++] 2048 (Easy)
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2
www.acmicpc.net
[문제 요약]
- 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
- <그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.
- <그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.
- 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
[문제 조건]
- 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.
- 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
- 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
- 시간 제한 : 1초
- 메모리 제한 : 512MB
[문제 풀이]
이번 문제는 N의 크기도 최대 20이거 움직이는 횟수도 최대 5번밖에 움직이지 않기 때문에 브루트포스 방식으로 해결할 수 있다.
필자는 4개의 방향에 대해 보드의 변화를 주는 함수를 각각 만들었고, DFS 방식으로 값을 구하였다.
큰 틀은 다음과 같다.
void solve(vector<vector<int>> mp, int depth)
{
if (depth == 5)
{
//
...
//
return;
}
vector<vector<int>> tmp = mp;
left_push(tmp); solve(tmp, depth + 1);
tmp = mp;
right_push(tmp); solve(tmp, depth + 1);
tmp = mp;
up_push(tmp); solve(tmp, depth + 1);
tmp = mp;
down_push(tmp); solve(tmp, depth + 1);
}모든 방향에 대해 이동시켜보고 5번까지 이동했으면 보드에서 가장 큰 수를 찾아 ans에 갱신해주면 된다.
그렇다면 제일 중요한 각 방향에 따른 갱신 함수를 살펴보자.
필자는 한 방향(왼쪽으로 밀었을때)에 대해서만 설명하고 나머지는 방향은 맨 밑 코드를 통해 이해해보자.
먼저 블럭들을 왼쪽으로 밀게 되면 같은 값을 갖는 블록들은 합쳐질 것이고 그렇지 않은 블록들은 왼쪽으로 이동하게 될 것이다.
이때 블록들을 어떤 순서로 왼쪽으로 옮기느냐가 중요하다.
블록을 왼쪽으로 민다고 가정하면 보드상에서 왼쪽에 있는 블록들이 먼저 움직여야 할 것이다.
왜냐하면 파란색 블록이 먼저 움직이게 되면 빨간색으로 표시한 부분에 막혀 더 진행하지 않게 된다. 하지만 실제로는 빨간색 부분이 움직이면서 생긴 공간까지 파란색이 이동할 수 있기 때문에 이동하고자 하는 방향에 있는 블록들부터 먼저 움직여야 한다.
결론적으로 왼쪽으로 밀면 (왼쪽->오른쪽) 오른쪽으로 밀면 (오른쪽->왼쪽) , 위로 밀면 (위->아래) , 아래로 밀면(아래->위)와 같이 블록들을 움직여줘야 된다.
여기서 헷갈리지 않아야 되는 부분이 블록들을 왼쪽에서 오른쪽으로 옮긴다는 의미가 아니라 왼쪽 블록부터 움직인다는 것을 주의하자.
또한 블록들을 움직이면서 같은 값을 갖는 블록들은 합쳐지게 되는데, 한 번 합쳐진 블록에 대해서는 더 이상 합쳐지지 않는 다는 것을 주의 해야 된다.
만약 예를들어 블록이 ( 2, 2, 4 ) 와 같이 주어져 있고 왼쪽으로 밀었을때 값이 8인 블록이 생기는 것이 아니라 (4, 4)와 같이 블록이 생긴다는 것을 주의해야 한다.
이 부분은 각 이동 함수 별로 합체 여부를 체크하는 배열을 하나 두어 관리 하였다.
[이동 함수(왼쪽으로 밀었을 때]
void left_push(vector<vector<int>>& mp)
{
vector<vector<bool>> ck(n, vector<bool>(n, 0));
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
int value = mp[i][j];
for (int h = 1; ; h++)
{
int nx = j - h;
if (nx < 0) { mp[i][j] = 0; mp[i][j - (h - 1)] = value; break; }
if (mp[i][nx] == 0) continue;
if (mp[i][nx] == value && !ck[i][nx]) { mp[i][nx] = value * 2; mp[i][j] = 0; ck[i][nx] = true; break; }
else { mp[i][j] = 0; mp[i][j - (h-1)] = value; break; }
}
}
}
}다른 방향은 i, j의 시작위치랑 순서등을 잘 조작하면 된다.
ck배열이 합체 여부 판단
[전체 소스 코드]
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <set>
#define INF 987654321
#define mod 1000000
#define pii pair<int,int>
using namespace std;
int n;
int ans = -1;
void up_push(vector<vector<int>>& mp)
{
vector<vector<bool>> ck(n, vector<bool>(n, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int value = mp[i][j];
for (int h = 1; ; h++)
{
int ny = i - h;
if (ny < 0) { mp[i][j] = 0; mp[i - (h - 1)][j] = value; break; }
if (mp[ny][j] == 0) continue;
if (mp[ny][j] == value && !ck[ny][j]) { mp[ny][j] = value * 2; mp[i][j] = 0; ck[ny][j] = true; break; }
else { mp[i][j] = 0; mp[i - (h - 1)][j] = value; break; }
}
}
}
}
void down_push(vector<vector<int>>& mp)
{
vector<vector<bool>> ck(n, vector<bool>(n, 0));
for (int i = n-1; i >= 0; i--)
{
for (int j = 0; j < n; j++)
{
int value = mp[i][j];
for (int h = 1; ; h++)
{
int ny = i + h;
if (ny >= n) { mp[i][j] = 0; mp[i + (h - 1)][j] = value; break; }
if (mp[ny][j] == 0) continue;
if (mp[ny][j] == value && !ck[ny][j]) { mp[ny][j] = value * 2; mp[i][j] = 0; ck[ny][j] = true; break; }
else { mp[i][j] = 0; mp[i + (h - 1)][j] = value; break; }
}
}
}
}
void left_push(vector<vector<int>>& mp)
{
vector<vector<bool>> ck(n, vector<bool>(n, 0));
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
int value = mp[i][j];
for (int h = 1; ; h++)
{
int nx = j - h;
if (nx < 0)
{
mp[i][j] = 0; mp[i][j - (h - 1)] = value; break;
}
if (mp[i][nx] == 0) continue;
if (mp[i][nx] == value && !ck[i][nx]) { mp[i][nx] = value * 2; mp[i][j] = 0; ck[i][nx] = true; break; }
else { mp[i][j] = 0; mp[i][j - (h-1)] = value; break; }
}
}
}
}
void right_push(vector<vector<int>>& mp)
{
vector<vector<bool>> ck(n, vector<bool>(n, 0));
for (int j = n-1; j >= 0; j--)
{
for (int i = 0; i < n; i++)
{
int value = mp[i][j];
for (int h = 1; ; h++)
{
int nx = j + h;
if (nx >= n) { mp[i][j] = 0; mp[i][j + (h - 1)] = value; break; }
if (mp[i][nx] == 0) continue;
if (mp[i][nx] == value && !ck[i][nx]) { mp[i][nx] = value * 2; mp[i][j] = 0; ck[i][nx] = true; break; }
else { mp[i][j] = 0; mp[i][j + (h - 1)] = value; break; }
}
}
}
}
void solve(vector<vector<int>> mp, int depth)
{
if (depth == 5)
{
int max_v = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
max_v = max(max_v, mp[i][j]);
}
}
ans = max(ans, max_v);
return;
}
vector<vector<int>> tmp = mp;
left_push(tmp); solve(tmp, depth + 1);
tmp = mp;
right_push(tmp); solve(tmp, depth + 1);
tmp = mp;
up_push(tmp); solve(tmp, depth + 1);
tmp = mp;
down_push(tmp); solve(tmp, depth + 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<vector<int>> mp;
cin >> n;
mp.resize(n); for (int i = 0; i < n; i++) mp[i].resize(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> mp[i][j];
solve(mp, 0);
cout << ans;
}
굳