[백준] 12100번: 2048 (Easy)

📌 문제

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

📌 설명

보드의 크기와 이동 횟수가 충분히 작으므로 백트래킹으로 해결할 수 있다. 까다로웠던 부분은 상, 하, 좌, 우로 불록을 이동시키는 것이었다. 처음에는 모든 이동 방향에 대한 움직임을 일일히 작성했는데, 하다보니 아닌 것 같았다. 따라서 블록 움직임에 대한 코드는 위로 움직이는 경우로 한정하여 작성하였고 나머지 방향은 보드를 돌리는 것으로 구현하였다.

📌 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector <vector<int>> arr(20, vector<int>(20));
int ans;

// 기본값은 위로 이동, 다른 방향일 경우 arr를 회전한다.
void moveUp() {
	vector<vector<int>> moved(20, vector<int>(20));

	for (int i = 0;i < n;i++) {
		int able = 0;
		int first = -1;
		int second = -1;
		for (int j = 0;j < n;j++) {
			if (arr[j][i] != 0) {
				if (first == -1)
					first = arr[j][i];
				else if (second == -1) {
					second = arr[j][i];

					if (first == second) {
						moved[able][i] = first + second;
						able++;
						first = -1;
						second = -1;
					}
					else {
						moved[able][i] = first;
						able++;
						first = second;
						second = -1;
					}
				}
			}

			if (j == n - 1 && first != -1) {
				moved[able][i] = first;
			}
		}
	}

	arr = moved;
}

// arr를 시계 방향으로 1회전
void clockwise() {
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			swap(arr[i][j], arr[j][i]);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n / 2; j++) {
			swap(arr[i][j], arr[i][n - j - 1]);
		}
	}
}

// arr를 시계 반대 방향으로 1회전
void counterClockwise() {
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			swap(arr[i][j], arr[j][i]);
		}
	}

	for (int j = 0; j < n; j++) {
		for (int i = 0; i < n / 2; i++) {
			swap(arr[i][j], arr[n - i - 1][j]);
		}
	}
}

void dfs(int k) {
	if (k == 5) {
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < n;j++) {
				ans = ans > arr[i][j] ? ans : arr[i][j];
			}
		}

		return;
	}

	vector<vector<int>> origin = arr;

	// 상
	moveUp();
	dfs(k + 1);
	arr = origin;

	// 하
	clockwise();
	clockwise();
	moveUp();
	counterClockwise();
	counterClockwise();
	dfs(k + 1);
	arr = origin;

	// 좌
	clockwise();
	moveUp();
	counterClockwise();
	dfs(k + 1);
	arr = origin;

	// 우
	counterClockwise();
	moveUp();
	clockwise();
	dfs(k + 1);
	arr = origin;
}

int main() {
	cin >> n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> arr[i][j];
		}
	}

	dfs(0);
	cout << ans;
}