BOJ 백준 12100 2048 (Easy)

https://www.acmicpc.net/problem/12100

< 2048 (Easy) >

 이 문제는 게임의 조건만 제대로 이해하면  푸는 데는 크게 어려울 것이 없는 문제이다.

< 조건 >

1. 현재 움직이려는 칸이 0인 경우는 빈칸이므로 고려하지 않는다. 

2. 현재 움직이려는 칸이 이동하려는 칸이 0인 경우

ex ) 

2 0 4       0 2 4  

0 0 0  ->  0 0 0

0 0 0       0 0 0

      

3. 현재 움직이려는 칸의 이동할 칸이 0 이 아닌 경우

3-1. 현재 움직이려는 칸과 이동할 칸의 값이 같은 경우

- 현재 움직인 칸을 0으로 만들어주고 이동할 칸의 값을 *2를 해준다.

- 단, 움직이려는 칸이나 이동하려는 칸이 이미 합쳐진 경우가 있다면, 그 칸은 더 이상 이동하지 못하므로 break

ex)

2 2 2 2    0 0 4 4    0 0 0 8

0 0 0 0    0 0 0 0    0 0 0 0

0 0 0 0    0 0 0 0    0 0 0 0

0 0 0 0    0 0 0 0    0 0 0 0

위의 예시처럼, 2 2 2 2 가 8로 하나가 되려면 2번의 이동이 필요하다.

이미 합쳐진 경우를 고려하기 위해서 게임 판 배열 사이즈만큼 배열을 하나 만들어 합쳐진 적이 있는지 체크해준다.

3-2. 현재 움직이려는 칸과 이동할 칸의 값이 다른 경우

- 움직일 수 없으므로 break.

4. 상, 하, 좌, 우를 모두 고려해보면서 재귀를 돌려준다.

상, 하, 좌, 우로 돌리기 전, 즉 for문을 들어가기 전에 배열을 그대로 복사해둔다.

5. 5번을 돌면 배열에서 가장 큰 값을 찾아 갱신해준다.

6. 재귀를 빠져나왔을 경우, 4번에서 복사해 둔 배열을 이용하여 원 상태로 돌린다.

#include <cstdio>
#include <cstring>

#define UP 0
#define LT 1
#define DW 2
#define RT 3

#define SIZE 21

int map[SIZE][SIZE];
int n;
int iMax = -1;

void copy(int (*temp)[SIZE]){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			temp[i][j] = map[i][j];
		}
	}
}
void back(int (*temp)[SIZE]){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			map[i][j] = temp[i][j];
		}
	}
}

void playing(int dir){
	bool IsMerge[SIZE][SIZE];
	memset(IsMerge, 0, sizeof(IsMerge));
	
	if(dir == UP){
		for(int i = 1; i < n ; i++){
			for(int j = 0; j < n; j++){
				for(int k = i; k >= 1; k--){
					if(map[k][j] == 0) break;
					
					if(map[k - 1][j] == 0){
						map[k - 1][j] = map[k][j];
						map[k][j] = 0;
					}
					else{
						if(IsMerge[k][j]) break;
						if(IsMerge[k - 1][j]) break;
						if(map[k - 1][j] != map[k][j]) break;
						
						map[k - 1][j] *= 2;
						map[k][j] = 0;
						IsMerge[k - 1][j] = true;
					}
				}
			}
		}
	}
	else if (dir == DW){
		for(int i = n - 2; i >= 0; i--){
			for(int j = 0; j < n; j++){
				for(int k = i; k < n - 1; k++){
					if(map[k][j] == 0) break;
					
					if(map[k + 1][j] == 0){
						map[k + 1][j] = map[k][j];
						map[k][j] = 0;
					}
					else{
						if(IsMerge[k][j]) break;
						if(IsMerge[k + 1][j]) break;
						if(map[k + 1][j] != map[k][j]) break;
						
						map[k + 1][j] *= 2;
						map[k][j] = 0;
						IsMerge[k + 1][j] = true;
					}
				}
			}
		}
	}
	else if (dir == LT){
		for(int i = 0; i < n; i++){
			for(int j = 1; j < n; j++){
				for(int k = j; k >= 1; k--){
					if(map[i][k] == 0) break;
					
					if(map[i][k - 1] == 0){
						map[i][k - 1] = map[i][k];
						map[i][k] = 0;
					}
					else{
						if(IsMerge[i][k]) break;
						if(IsMerge[i][k - 1]) break;
						if(map[i][k - 1] != map[i][k]) break;
						
						map[i][k - 1] *= 2;
						map[i][k] = 0;
						IsMerge[i][k - 1] = true;
					}
				}
			}
		}
	}
	else if (dir == RT){
		for(int i = 0; i < n; i++){
			for(int j = n - 2; j >= 0; j--){
				for(int k = j; k < n - 1; k++){
					if(map[i][k] == 0) break;
					
					if(map[i][k + 1] == 0){
						map[i][k + 1] = map[i][k];
						map[i][k] = 0;
					}
					else{
						if(IsMerge[i][k]) break;
						if(IsMerge[i][k + 1]) break;
						if(map[i][k + 1] != map[i][k]) break;
						
						map[i][k + 1] *= 2;
						map[i][k] = 0;
						IsMerge[i][k + 1] = true;
					}
				}
			}
		}
	}
} 

void solution(int num){
	if(num == 5){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(map[i][j] > iMax) iMax = map[i][j];
			}
		}
		return;
	}
	
	int temp[SIZE][SIZE];
	copy(temp);
	
	for(int i=0; i<4; i++){
		playing(i);
		solution(num + 1);
		back(temp);
	}
}

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			scanf("%d", &map[i][j]);
			if(map[i][j] > iMax) iMax = map[i][j];
		}
	}
	solution(0);
	printf("%d\n", iMax);
	
	return 0;
}