2048을 구현하는 문제이다. 우선 상하좌우를 구현해주었다. 현재 위치 다음 값이 0일 경우 다음으로 이동시켜주고, 현재 위치와 같은 값이면 두 값을 합쳐주고 현재 위치를 0으로 바꿔준다. 여기서 주의할 점은 한번의 이동 내에서 한번 합쳐진 경우 두번은 합쳐지면 안되는 것이다. 그래서 check
를 통해 이를 확인해준다. check
값 또한 이동시 같이 이동시켜준다. 이를 dfs를 통해 백트래킹을 하면서 모든 경우를 돌면서 최댓값을 찾아 출력해주었다.
굉장히 시간이 오래 걸렸다. 처음에는 2045을 잘못 이해하고 있었다. 2 2 2
인 경우 왼쪽으로 이동하면 4 2 0
이 되어야 하는데 2 4 0
이 되도록 구현했었다. 두번째는 첫번재 문제를 고치는 과정에 반복문 범위를 잘못 입력하였고 이를 몰라 문제를 다른 곳에서 찾느라 시간 낭비가 심했다. 구현 문제 자체가 시간이 오래 걸리고 오타가 많을 수 있기때문에 충분히 주의해야겠다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N, res = 0;
int A[20][20];
void up(int a[][20]) {
bool check[20][20];
memset(check, false, sizeof(check));
for (int j = 0; j < N; j++) {
while (1) {
bool tf = false;
for (int i = 1; i < N; i++) {
if (a[i][j] == 0) continue;
if (a[i - 1][j] == 0) {
a[i - 1][j] = a[i][j];
a[i][j] = 0;
tf = true;
if (check[i][j]) {
check[i - 1][j] = true;
check[i][j] = false;
}
}
else if (a[i - 1][j] == a[i][j] && !check[i - 1][j] && !check[i][j]) {
a[i - 1][j] += a[i][j];
a[i][j] = 0;
tf = true;
check[i - 1][j] = true;
}
}
if (!tf) break;
}
}
}
void down(int a[][20]) {
bool check[20][20];
memset(check, false, sizeof(check));
for (int j = 0; j < N; j++) {
while (1) {
bool tf = false;
for (int i = N-2; i >= 0; i--) {
if (a[i][j] == 0) continue;
if (a[i + 1][j] == 0) {
a[i + 1][j] = a[i][j];
a[i][j] = 0;
tf = true;
if (check[i][j]) {
check[i + 1][j] = true;
check[i][j] = false;
}
}
else if (a[i + 1][j] == a[i][j] && !check[i+1][j] && !check[i][j]) {
a[i + 1][j] += a[i][j];
a[i][j] = 0;
tf = true;
check[i + 1][j] = true;
}
}
if (!tf) break;
}
}
}
void left(int a[][20]) {
bool check[20][20];
memset(check, false, sizeof(check));
for (int i = 0; i < N; i++) {
while (1) {
bool tf = false;
for (int j = 1; j < N; j++) {
if (a[i][j] == 0) continue;
if (a[i][j - 1] == 0) {
a[i][j - 1] = a[i][j];
a[i][j] = 0;
tf = true;
if (check[i][j]) {
check[i][j - 1] = true;
check[i][j] = false;
}
}
else if (a[i][j - 1] == a[i][j] && !check[i][j-1] && !check[i][j]) {
a[i][j - 1] += a[i][j];
a[i][j] = 0;
tf = true;
check[i][j - 1] = true;
}
}
if (!tf) break;
}
}
}
void right(int a[][20]) {
bool check[20][20];
memset(check, false, sizeof(check));
for (int i = 0; i < N; i++) {
while (1) {
bool tf = false;
for (int j = N-2; j >= 0; j--) {
if (a[i][j] == 0) continue;
if (a[i][j + 1] == 0) {
a[i][j + 1] = a[i][j];
a[i][j] = 0;
tf = true;
if (check[i][j]) {
check[i][j + 1] = true;
check[i][j] = false;
}
}
else if (a[i][j + 1] == a[i][j] && !check[i][j+1] && !check[i][j]) {
a[i][j + 1] += a[i][j];
a[i][j] = 0;
tf = true;
check[i][j + 1] = true;
}
}
if (!tf) break;
}
}
}
void dfs(int depth, int a[][20]) {
if (depth == 5) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
res = max(res, a[i][j]);
}
}
return;
}
int tmp[20][20];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
tmp[i][j] = a[i][j];
}
}
for (int i = 0; i < 4; i++) {
switch (i) {
case 0:
up(a);
break;
case 1:
down(a);
break;
case 2:
left(a);
break;
case 3:
right(a);
break;
}
dfs(depth + 1, a);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
a[i][j] = tmp[i][j];
}
}
}
}
void solution() {
dfs(0, A);
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}