[C++] 백준 12100 : 2048 (Easy)

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

12100번: 2048 (Easy)

백준 12100번 2048 (Easy) 문제를 풀었다.

 

처음에 백트래킹으로 구현을 했는데 promising한 조건을 정하지 못해서 그냥 구현 문제를 푸는 것 처럼 됐다.

 

Move함수는 입력받은 좌표와 방향으로 숫자를 옮긴다. 재귀적으로 구현을 했다.

왼쪽으로 Move한다면

1. 입력받은 좌표의 숫자가 0인지 체크한다.

 

1.1 입력받은 좌표의 숫자가 0일 때,

1.1.1 보드판 끝까지 오른쪽으로 탐색하는데 모든 숫자가 0일 때 아무것도 하지 않는다.

1.1.2 제일 가까이 있는 0이 아닌 숫자와 입력받은 좌표의 숫자(0)를 swap한다.

 

1.2 입력받은 좌표의 숫자가 0이 아닐 때,

1.2.1 보드판 끝까지 오른쪽으로 탐색하는데 모든 숫자가 0일 때 아무것도 하지 않는다.

1.2.2 제일 가까이 있는 0이 아닌 숫자(A)가 입력받은 좌표와 같은지 체크한다.

 

1.2.2.1 탐색 결과가 입력받은 좌표의 숫자와 같다면 해당 좌표가 변한 적 있는지 체크한다.

1.2.2.1.1 입력받은 좌표가 변한 적 있다면 입력받은 좌표 오른쪽에 A를 위치시키고 A가 있던 좌표의 숫자를 0으로 바꾼다.

1.2.2.1.2 입력받은 좌표가 변한 적 없다면 입력받은 좌표의 숫자를 2배로 바꾸고 A가 있던 좌표의 숫자를 0으로 바꾼다.

 

1.2.2.2 입력받은 좌표와 다르다면 입력받은 좌표 오른쪽에 A를 위치시키고 A가 있던 좌표의 숫자를 0으로 바꾼다.

 

2 입력받은 좌표의 원래 숫자가 바뀌었는지 체크한다.

2.1 원래 숫자가 바뀌었다면 재귀적으로 Move를 다시 실행한다.

2.2 원래 숫자 그대로라면 Move 함수를 종료한다.

 

해당 작업을 모든 좌표에 실행해서 해결했다.

 

보드를 움직이기 전에 원래 보드의 값들을 map_temp변수에 옮겨야 한다.

그 다음 BT함수를 level을 증가시켜서 실행시키고 함수가 끝나면

map_temp변수에 있던 기존 값을 다시 map에 복구하는 작업을 해야한다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000

struct Cell {
	int x;
	int y;
	int num;
};

int n;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[20][20];
int turn_max[5];

void Print_Board() {
	cout << '\n';
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
}

int Find_max() {
	int max_num = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (max_num < map[i][j])
				max_num = map[i][j];
		}
	}
	return max_num;
}

Cell Scan_Num(int row, int col, int dir_x, int dir_y) {
	while (map[row][col] == 0) {		
		row += dir_x;
		col += dir_y;
		if (row >= n || col >= n || row < 0 || col < 0) {
			row -= dir_x;
			col -= dir_y;
			break;
		}
	}
	return { row,col,map[row][col] };
}

void Move(int row, int col, int dir_x,int dir_y, int origin_num, int changed) {
	if (map[row][col] == 0) {
		Cell res = Scan_Num(row, col, dir_x, dir_y);
		if (res.num == 0) {

		}
		else {
			map[row][col] = res.num;
			map[res.x][res.y] = 0;
		}
	}
	else {
		Cell res = Scan_Num(row + dir_x, col + dir_y, dir_x, dir_y);
		if (res.num == 0) {

		}
		else {
			if (map[row][col] == res.num) {
				if (changed == 1) {
					map[res.x][res.y] = 0;
					map[row + dir_x][col + dir_y] = res.num;
				}
				else {
					changed = 1;
					map[row][col] = 2 * res.num;
					map[res.x][res.y] = 0;
				}
			}
			else {
				map[res.x][res.y] = 0;
				map[row+ dir_x][col + dir_y] = res.num;
			}
		}
	}

	if (origin_num == map[row][col])
		return;

	Move(row, col, dir_x, dir_y, map[row][col],changed);
}

void Left() {
	int dir_x = dx[0];
	int dir_y = dy[0];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Move(i, j, dir_x, dir_y, map[i][j],0);
		}
	}
}

void Up() {
	int dir_x = dx[2];
	int dir_y = dy[2];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			Move(i, j, dir_x, dir_y, map[i][j],0);
		}
	}
}

void Right() {
	int dir_x = dx[1];
	int dir_y = dy[1];
	for (int i = n-1; i >=0 ; i--) {
		for (int j = n-1; j >=0; j--) {
			Move(i, j, dir_x, dir_y, map[i][j],0);
		}
	}
}

void Down() {
	int dir_x = dx[3];
	int dir_y = dy[3];
	for (int i = n - 1; i >= 0; i--) {
		for (int j = n - 1; j >= 0; j--) {
			Move(i, j, dir_x, dir_y, map[i][j],0);
		}
	}
}

void Direction(int type) {
	switch (type)
	{
	case 0:
		Left();
		break;
	case 1:
		Up();
		break;
	case 2:
		Right();
		break;
	case 3:
		Down();
		break;
	default:
		break;
	}
}

void BT(int level) {
	if (level == 5) {
		return;
	}

	int max_temp;
	int map_temp[20][20];
	int map_size = 400;

	for (int i = 0; i < 4; i++) {
		copy(&map[0][0], &map[0][0] + map_size, &map_temp[0][0]);

		Direction(i);

		max_temp = Find_max();
		if (turn_max[level] < max_temp)
			turn_max[level] = max_temp;

		BT(level + 1);

		copy(&map_temp[0][0], &map_temp[0][0] + map_size, &map[0][0]);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	BT(0);

	cout << turn_max[4];

	return 0;
}