[성실코딩 4일차] 백준 #12100 2048 (Easy) *

진짜 오래 걸려서 풀었다.

까다롭고 내가 놓치는 예외 경우가 많아서 힘들었다 ㅠㅠ

문제 풀이

DFS 로 타고 들어가면서 

위, 아래, 오른쪽, 왼쪽  4방향으로 다 이동시키면서

depth = 5 ( 5번 이동하였을) 때, 가장 큰 블록의 값을 저장하였다.

만약 문제에서 최대 5번이 아니라 더 이동하거나, 

보드의 크기가 20 초과라면,

DFS로 풀지 못하고 규칙성을 찾아서 더 빠르게 풀어야할 것 같다.

C언어 구현 코드

#include < iostream >

using namespace std;

int N;
int maximum = 0;

int getTheBiggist(int _map[20][20]) {

	int v = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (v < _map[i][j]) {
				v = _map[i][j];
			}
		}
	}
	return v;
}

// _b : 방향 
// 0 : 위
// 1 : 아래
// 2 : 오른쪽 ->
// 3 : 왼쪽 <-
void func(int _depth, int _b, int _map[20][20]) {

	int map[20][20] = {0,};
	
	switch (_b)
	{
	case 0: // 위
		for (int c = 0; c < N; c++) {
			int new_r = 0;
			for (int r = 0; r < N; r++) {
				int temp = _map[r][c];

				if (temp != 0) {
					// 비교할 다음 r 찾아야 돼.
					int next_r = r + 1;
					while (next_r < N) {
						if (_map[next_r][c] != 0) break;
						next_r++;
					}

					if (next_r < N && temp == _map[next_r][c]) {
							map[new_r][c] = 2 * temp;
							r = next_r;
					}
					else {
						map[new_r][c] = temp;
					}
					new_r++;
				}
			}
		}
		break;
	case 1: // 아래
		for (int c = 0; c < N; c++) {
			int new_r = N - 1;
			for (int r = N - 1; r > -1; r--) {
				int temp = _map[r][c];

				if (temp != 0) {
					int next_r = r - 1;
					while (next_r > -1) {
						if (_map[next_r][c] != 0) break;
						next_r--;
					}

					if (next_r > -1 && temp == _map[next_r][c]) {
							map[new_r][c] = 2 * temp;
							r = next_r;
					}
					else {
						map[new_r][c] = temp;
					}
					new_r--;
				}
			}
		}
		break;
	case 2: // 오른쪽 ->
		for (int r = 0; r < N; r++) {
			int new_c = N - 1;
			for (int c = N - 1; c > -1; c--) {
				int temp = _map[r][c];

				if (temp != 0) {

					int next_c = c - 1;
					while (next_c > -1) {
						if (_map[r][next_c] != 0) break;
						next_c--;
					}

					if ( next_c > -1 && temp == _map[r][next_c]) {
						map[r][new_c] = 2 * temp;
						c = next_c;
					}
					else {
						map[r][new_c] = temp;
					}
					new_c--; 
				}
			}
		}
		break;
	case 3: // 왼쪽  <-
		for (int r = 0; r < N; r++) {
			int new_c = 0;
			for (int c = 0; c < N; c++) {
				int temp = _map[r][c];

				if (temp != 0) {

					int next_c = c + 1;
					while (next_c < N) {
						if (_map[r][next_c] != 0) break;
						next_c++;
					}

					if ( next_c < N && temp == _map[r][next_c]) {
						map[r][new_c] = 2 * temp;
						c = next_c;
					}
					else {
						map[r][new_c] = temp;
					}
					new_c++;
				}
			}
		}
		break;
	}

	if (_depth == 4) { // 탈출 조건 0,1,2,3,4
		int value = getTheBiggist(map);
		if (value > maximum) {
			maximum = value;
		}
		return;
	}

	for (int b = 0; b < 4; b++) {
		func(_depth + 1, b, map);
	}
}

int main(void) {
	
	int map[20][20];
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int b = 0; b < 4; b++) {
		func(0, b, map);
	}

	cout << maximum << endl;

	return 0;
}