백준 - 마법사 상어와 블리자드 (21611번)

백준 - 마법사 상어와 블리자드 (21611번)

Index를 읽는 규칙만 찾으면 금방 구현할 수 있다.
(OutofBounds를 만나서 여러번 실패하긴했지만 ㅎ.ㅎ.)

위 그림처럼 direction은 좌, 하, 우, 상 순서로 바뀌고
그 때마다 옮겨지는 range는 1, 1, 2, 2, 3, 3, 4, 4.. 순서로 증가한다.

이 규칙을 이용해서 2차원 배열을 1차원 배열로 projection해주면 된다.

그 이후에 연속된 것을 터뜨리기 위해서 같은 숫자가 4개 이상 연속되었을 때, 해당 숫자들을 -1로 바꿔준다.
그 이후 벡터를 처음부터 다시 읽으면서 -1이 아닌 것들을 새로 담고, 다시 연속된 것을 터뜨린다.

더 이상 터뜨릴 것이 없으면 이제 다시 2차원 배열을 만들기 위해서 숫자를 Count해준다.

그 이후 다시 2차원 배열에 Remapping 해주는데, 위 그림처럼 규칙을 가지고 (0, 0)을 만나거나 혹은 1차원 배열의 크기만큼 반복해주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n, m;
int map[50][50];
int magic[105][2];

int magicRowDir[4] = { -1, 1, 0, 0 };
int magicColDir[4] = { 0, 0, -1, 1 };
int rowDir[4] = { 0, 1, 0, -1 };
int colDir[4] = { -1, 0, 1, 0 };
void Print_Map(const char *s)
{
	printf("%s \n", s);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d \t", map[i][j]);
		}
		printf("\n");
	}
}
int baseRow;
int baseCol;
int result;

void projection_func(vector<int> &arr)
{
	int nrow = baseRow;
	int ncol = baseCol;
	int len = 1, iter = 0, dir = 0;
	while (1) {
		for (int i = 0; i < len; i++) {
			nrow = nrow + rowDir[dir];
			ncol = ncol + colDir[dir];
			if (map[nrow][ncol] == 0) 
				return;
			if (map[nrow][ncol] != -1)
				arr.push_back(map[nrow][ncol]);
			if (nrow == 0 && ncol == 0) 
				return;
		}
		if (iter % 2 == 1)
			len++;
		iter++;
		dir = (dir + 1) % 4;
	}
}

void bomb_func(vector<int> &arr)
{
	while (1) {
		bool is_occur = false;
		for (int i = 0; i < arr.size(); i++) {
			if (arr[i] == -1)
				continue;
			int base = arr[i];
			int same_count = 1;
			for (int j = i + 1; j < arr.size(); j++) {
				if (arr[j] != base)
					break;
				same_count++;
			}
			if (same_count < 4)
				continue;
			is_occur = true;
			result = result + (same_count * base);
			for (int j = i; j < i + same_count; j++)
				arr[j] = -1;
		}

		vector<int> tmp;
		for (int i = 0; i < arr.size(); i++) 
			if (arr[i] != -1)
				tmp.push_back(arr[i]);
		
		arr.swap(tmp);
		if (!is_occur)
			break;
	}
}
void same_count_func(vector<int>& arr)
{
	vector<int> tmp;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == -1)
			continue;
		int base = arr[i];
		arr[i] = -1;
		int same_count = 1;
		for (int j = i + 1; j < arr.size(); j++) {
			if (arr[j] != base)
				break;
			arr[j] = -1;
			same_count++;
		}
		tmp.push_back(same_count);
		tmp.push_back(base);
	}
	if (arr.empty())
		return;
	arr.swap(tmp);
}
void remapping_func(vector<int> &arr)
{
	for (int i = 0; i < 50; i++)
		memset(map[i], 0, sizeof(map[i]));
	if (arr.empty())
		return;
	int nrow = baseRow;
	int ncol = baseCol;
	int len = 1, iter = 0, dir = 0, idx = 0;
	while (1) {
		for (int i = 0; i < len; i++) {
			nrow = nrow + rowDir[dir];
			ncol = ncol + colDir[dir];
			map[nrow][ncol] = arr[idx++];
			if (nrow == 0 && ncol == 0) 
				return;
			if (idx == arr.size()) 
				return;
		}
		if (iter % 2 == 1)
			len++;
		iter++;
		dir = (dir + 1) % 4;
	}
}
void solve()
{
	vector<int> arr;
	projection_func(arr);
	bomb_func(arr);
	same_count_func(arr);
	remapping_func(arr);
}
int main(void)
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			cin >> map[i][j];

	for (int i = 0; i < m; i++) 
		cin >> magic[i][0] >> magic[i][1];

	baseRow = (n - 1) / 2;
	baseCol = (n - 1) / 2;
	for (int i = 0; i < m; i++) {
		int nrow = baseRow;
		int ncol = baseCol;
		for (int j = 0; j < magic[i][1]; j++) {
			nrow = nrow + magicRowDir[magic[i][0] - 1];
			ncol = ncol + magicColDir[magic[i][0] - 1];
			map[nrow][ncol] = -1;
		}
		solve();
	}

	cout << result << "\n";

	return 0;
}