백준 12100번 : 2048(Easy)

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

#include <iostream>
#include <cstring>
#define max(a,b) a>b ? a : b

using namespace std;

int n = 0;
int ans = 0;
int board[20][20];

// 보드에서 최대값 찾기
int getMax() {
	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			result = max(result, board[i][j]);
		}
	}

	return result;
}

// 오른쪽 이동 : 모든 행에 대해 맨 오른쪽 열부터 왼쪽 열로
void toRight() {
	
	/* 모든 행에 대해 */
	for (int i = 0; i < n; i++) { 
		int sumpoint = n - 1; // 합체한다면 그 블록의 위치
		int curpoint = n - 1; // 현재 블록의 위치

		while (true) {
			if (curpoint < 0) break;

			/* 현재 블록이 0이 아니면 탐색시작 */
			if (board[i][curpoint]) { 

				bool flag = true;
				/* 맨 오른쪽 열부터 왼쪽 열로 */
				for (int j = curpoint - 1; j >= 0; j--) { 
					
					// 1. 한칸 전진해서 같은 블록을 만났다
					if (board[i][curpoint] == board[i][j]) {
						board[i][sumpoint] = board[i][j] * 2;
						board[i][j] = 0;
						board[i][curpoint] = 0;
						flag = false; // 이미 합체했으니 또 못한단 뜻
						break;
					}

					// 2. 한칸 전진해서 다른 블록을 만났다
					if (board[i][curpoint] != board[i][j] && board[i][j]) {
						break;
					}
				}

				// 합체 못한 블록들을 방향으로 밀어준다
				if (flag && sumpoint != curpoint) {
					board[i][sumpoint] = board[i][curpoint];
					board[i][curpoint] = 0;
				}
				sumpoint--;
				curpoint--;
			}

			/* 현재 블록이 0이면 탐색 안 함 */
			else {
				curpoint--;
			}
		}
	}
}

// 왼쪽 이동 : 모든 행에 대해 맨 왼쪽 열부터 오른쪽 열로
void toLeft() {

	/* 모든 행에 대해 */
	for (int i = 0; i < n; i++) {
		int sumpoint = 0; // 합체한다면 그 블록의 위치
		int curpoint = 0; // 현재 블록의 위치

		while (true) {
			if (curpoint > n - 1) break;

			/* 현재 블록이 0이 아니면 탐색시작 */
			if (board[i][curpoint]) {

				bool flag = true;
				/* 맨 왼쪽 열부터 오른쪽 열로 */
				for (int j = curpoint + 1; j < n; j++) {

					// 1. 한칸 전진해서 같은 블록을 만났다
					if (board[i][curpoint] == board[i][j]) {
						board[i][sumpoint] = board[i][j] * 2;
						board[i][j] = 0;
						board[i][curpoint] = 0;
						flag = false; // 이미 합체했으니 또 못한단 뜻
						break;
					}

					// 2. 한칸 전진해서 다른 블록을 만났다
					if (board[i][curpoint] != board[i][j] && board[i][j]) {
						break;
					}
				}

				// 합체 못한 블록들을 방향으로 밀어준다
				if (flag && sumpoint != curpoint) {
					board[i][sumpoint] = board[i][curpoint];
					board[i][curpoint] = 0;
				}
				sumpoint++;
				curpoint++;
			}

			/* 현재 블록이 0이면 탐색 안 함 */
			else {
				curpoint++;
			}
		}
	}
}


// 위쪽 이동 : 모든 열에 대해 맨 위쪽 행부터 아래쪽 행으로
void toUp() {
	/* 모든 열에 대해 */
	for (int i = 0; i < n; i++) {
		int sumpoint = 0; // 합체한다면 그 블록의 위치
		int curpoint = 0; // 현재 블록의 위치

		while (true) {
			if (curpoint > n - 1) break;

			/* 현재 블록이 0이 아니면 탐색시작 */
			if (board[curpoint][i]) {

				bool flag = true;
				/* 맨 위쪽 행부터 아래쪽 행으로 */
				for (int j = curpoint + 1; j < n; j++) {

					// 1. 한칸 전진해서 같은 블록을 만났다
					if (board[j][i] == board[curpoint][i]) {
						board[sumpoint][i] = board[j][i] * 2;
						board[j][i] = 0;
						board[curpoint][i] = 0;
						flag = false;
						break;
					}

					// 2. 한칸 전진해서 다른 블록을 만났다
					if (board[j][i] != board[curpoint][i] && board[j][i]) {
						break;
					}
				}

				// 합체 못한 블록들을 방향으로 밀어준다
				if (flag && sumpoint != curpoint) {
					board[sumpoint][i] = board[curpoint][i];
					board[curpoint][i] = 0;
				}
				sumpoint++;
				curpoint++;
			}

			/* 현재 블록이 0이면 탐색 안 함 */
			else {
				curpoint++;
			}
		}
	}
}

// 아래쪽 이동 : 모든 열에 대해 맨 아래쪽 행부터 위쪽 행으로
void toDown() {

	/* 모든 열에 대해 */
	for (int i = 0; i < n; i++) {
		int sumpoint = n - 1; // 합체한다면 그 블록의 위치
		int curpoint = n - 1; // 현재 블록의 위치

		while (true) {
			if (curpoint < 0) break;

			/* 현재 블록이 0이 아니면 탐색시작 */
			if (board[curpoint][i]) {

				bool flag = true;
				/* 맨 아래쪽 행부터 위쪽 행으로 */
				for (int j = curpoint - 1; j >= 0; j--) {

					// 1. 한칸 전진해서 같은 블록을 만났다
					if (board[curpoint][i] == board[j][i]) {
						board[sumpoint][i] = board[j][i] * 2;
						board[j][i] = 0;
						board[curpoint][i] = 0;
						flag = false; // 이미 합체했으니 또 못한단 뜻
						break;
					}

					// 2. 한칸 전진해서 다른 블록을 만났다
					if (board[curpoint][i] != board[j][i] && board[j][i]) {
						break;
					}
				}

				// 합체 못한 블록들을 방향으로 밀어준다
				if (flag && sumpoint != curpoint) {
					board[sumpoint][i] = board[curpoint][i];
					board[curpoint][i] = 0;
				}
				sumpoint--;
				curpoint--;
			}

			/* 현재 블록이 0이면 탐색 안 함 */
			else {
				curpoint--;
			}
		}
	}
}

// 블록들 이동
void moveBlocks(int dir) {
	// dir 0:오른쪽, 1:왼쪽, 2:위, 3:아래
	if (dir == 0) 
		toRight();
	if (dir == 1)
		toLeft();
	if (dir == 2)
		toUp();
	if (dir == 3)
		toDown();
	return;
}

// DFS로 5번 이동한 모든 경우의 수 탐색
void dfs(int level) {
	if (level == 5) {
		int result = getMax();
		ans = max(result, ans);
	}

	int board_copy[20][20] = { 0, };
	memcpy(board_copy, board, sizeof(board));
	for (int i = 0; i < 4; i++) {
		moveBlocks(i);
		dfs(level + 1);
		memcpy(board, board_copy, sizeof(board));
	}
}

int main() {
	cin >> n; // 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	} //입력

	dfs(0);
	cout << ans << '\n';
	return 0;
}