[백준] 12100번: 2048 (Easy)

📌 문제

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

📌 설명

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

최대 5번의 이동을 고려하며, 각 이동에서 4가지 방향으로 분기가 발생한다. 따라서 전체 경우의 수는 $4^5=1024$이다. moveUp, clockwise, counterClockwise 함수의 시간복잡도는 $O(N^2)$이다. 즉, 각 단계의 각 방향을 처리할 때의 시간복잡도는 $O(N^2)$이다. 전체 시간복잡도 또한 $O(N^2)$이나, 총 연산의 수를 계산해보자면 $1024 \times 20^2=409600$으로, 어쨌든 1초 내로 수행 가능하다.

📌 코드

#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;
}