백준 12100 : 2048 (Easy)

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

12100번: 2048 (Easy)

 

2048 게임 구현 문제다.

 

주의해야 할 점은 두 가지 정도이다.

 

1. 이동하는 방향의 제일 앞에 있는 블럭부터 움직일 것

2. 같은 숫자는 합치되, 이미 해당 턴에서 합쳐진 블럭이 다시 합쳐지지 않도록 할 것

 

완탐, 백트래킹으로 풀면 된다.

 

#include <iostream>
#include <algorithm>

#define max(a,b) a>b?a:b
using namespace std;

int n;
int board[20][20];
int max_val;

void copy(int from[][20], int to[][20]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			to[i][j] = from[i][j];
		}
	}
}

void simulate(int dir) {
	int cur;
    // 한 번 합쳐진 블럭이 해당 턴에서 다시 합쳐지지 않게 하기 위한 변수
	bool merged;

	if (dir == 0) {
		for (int i = 0; i < n; i++) {
			merged = 0;
            // 이동 방향의 제일 앞에있는 블럭부터 움직임
			for (int j = n - 2; j >= 0; j--) {
				if (!board[i][j]) continue;
				cur = j;
				while (cur + 1 < n) {
					if (board[i][cur + 1]) {
						if (!merged && board[i][cur + 1] == board[i][cur]) {
							board[i][cur + 1] *= 2;
							board[i][cur] = 0;
							merged = 1;
						}
						else merged = 0;
						break;
					}
					else {
						board[i][cur + 1] = board[i][cur];
						board[i][cur] = 0;
					}
					++cur;
				}
			}
			for (int j = 0; j < n; j++) {
				if (board[i][j] < 0) board[i][j] *= -1;
			}
		}
	}
	else if (dir == 1) {
		for (int i = 0; i < n; i++) {
			merged = 0;
			for (int j = 1; j < n; j++) {
				if (!board[i][j]) continue;
				cur = j;
				while (cur - 1 >= 0) {
					if (board[i][cur - 1]) {
						if (!merged && board[i][cur] == board[i][cur - 1]) {
							board[i][cur - 1] *= 2;
							board[i][cur] = 0;
							merged = 1;
						}
						else merged = 0;
						break;
					}
					else {
						board[i][cur - 1] = board[i][cur];
						board[i][cur] = 0;
					}
					--cur;

				}
			}
			for (int j = 0; j < n; j++) {
				if (board[i][j] < 0) board[i][j] *= -1;
			}
		}
	}
	else if (dir == 2) {
		for (int i = 0; i < n; i++) {
			merged = 0;
			for (int j = n - 2; j >= 0; j--) {
				if (!board[j][i]) continue;
				cur = j;
				while (cur + 1 < n) {
					if (board[cur + 1][i]) {
						if (!merged && board[cur][i] == board[cur + 1][i]) {
							board[cur + 1][i] = -board[cur + 1][i] * 2;
							board[cur][i] = 0;
							merged = 1;
						}
						else merged = 0;
						break;
					}
					else {
						board[cur + 1][i] = board[cur][i];
						board[cur][i] = 0;
					}
					++cur;
				}
			}
			for (int j = 0; j < n; j++) {
				if (board[j][i] < 0) board[j][i] *= -1;
			}
		}
	}
	else {
		for (int i = 0; i < n; i++) {
			merged = 0;
			for (int j = 0; j < n; j++) {
				if (!board[j][i]) continue;
				cur = j;
				while (cur - 1 >= 0) {
					if (board[cur - 1][i]) {
						if (!merged > 0 && board[cur][i] == board[cur - 1][i]) {
							board[cur - 1][i] = -board[cur - 1][i] * 2;
							board[cur][i] = 0;
						}
						else merged = 0;
						break;
					}
					else {
						board[cur - 1][i] = board[cur][i];
						board[cur][i] = 0;
					}
					--cur;
				}
			}
			for (int j = 0; j < n; j++) {
				if (board[j][i] < 0) board[j][i] *= -1;
			}
		}
	}
}

void dfs(int len) {
	if (len >= 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				max_val = max(max_val, board[i][j]);
			}
		}
		return;
	}

	// 백트래킹을 위해 현재 정보를 저장
	int cur_board[20][20];
	copy(board, cur_board);
    
	for (int i = 0; i < 4; i++) {
		copy(cur_board, board);
		simulate(i);
		dfs(len + 1);
	}
}

void solution() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}

	dfs(0);
	cout << max_val << '\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2024 kb

시간: 4 ms