[백준 21611] 마법사 상어와 블리자드 (C++)

문제 링크: https://www.acmicpc.net/problem/21611

21611번: 마법사 상어와 블리자드

1. 주의할 점

- 구현할 부분이 많다

- 구슬을 어떻게 당길 것인가?

- '파괴된'과 '폭파된' 구슬은 같지 않다

 

2. 구현

- Info 객체를 이용하여 1~Num^2-1까지 구슬의 위치를 V[] 배열에 담는다

- Arr[][]를 이용하여 현재 격자에 존재하는 구슬의 번호를 나타낸다

- Init() 함수를 이용하여 V[] 배열을 채운다

- M번 동안 지문에서 말한 순서대로 수행한다

- blizard() 함수를 이용하여 블리자드를 수행했을 때 Arr[][]의 상태를 수정한다

- getTight() 함수를 이용하여 사라진 구슬을 제외하고 구슬을 Marble 벡터에 담는다

- bombContinMarble() 함수를 이용하여 같은 구슬이 연속으로 4개 이상 존재한다면 폭파시킨다. 폭파될 때, marbleBombed[폭파된 구슬의 번호] 배열에 폭파된 수만큼 더한다

- setMarble2Arr() 함수를 이용하여 Marble 벡터에 저장되어 있는 구슬을 Arr[][]배열에 재배열 시킨다. 이때, 벡터의 크기가 Num^2-1보다 작다면 나머지는 0으로 채운다. 반대로 Num^2-1보다 크다면 Num^2-1만큼만 배열에 채운다

- 위 3개의 함수를 더 이상 폭파시킬 구슬이 없을 때까지 수행한다

- changeMarble()를 통해 구슬을 변화시킨다

- setMarble2Arr()를 다시 한번 수행하여 Arr[][] 배열을 수정한다

- M번의 수행이 끝났다면 Cal() 함수를 통해 결과값을 도출한다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
	int y, x;
};
info v[50 * 50];
int arr[49][49];
int num, m, d, sx, sy, answer = 0, dir, s;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int mvDir[4] = { 2,1,3,0 };
int marbleBombed[4];		//폭발한 구슬 수
vector<int> marble;
bool bombed;

void init() {
	int cx = sx;
	int cy = sy;
	int maxCount = num * num - 1;
	int len = 1;
	int cd = 0;
	int cnt = 1;
	while (1) {
		for (int k = 0; k < 2; k++) {
			for (int i = 0; i < len; i++) {
				cx += dx[mvDir[cd]];
				cy += dy[mvDir[cd]];
				v[cnt].y = cy;
				v[cnt].x = cx;
				cnt++;
			}
			if (cnt >= maxCount) break;
			cd = (cd + 1) % 4;
		}
		if (cnt >= maxCount) break;
		len++;
	}
}

void cal() {
	for (int i = 1; i < 4; i++)
		answer += (marbleBombed[i] * i);
}

void blizard() {
	int cx = sx;
	int cy = sy;
	while (s--) {
		cx += dx[dir];
		cy += dy[dir];
		arr[cy][cx] = 0;
	}
}

void bombContinMarble() {
	vector<int> dup, tmp;
	int val = -1;
	for (int i = 0; i < marble.size(); i++) {
		int mv = marble[i];
		if (val != mv) {
			if (tmp.size() < 4) {
				for (int j = 0; j < tmp.size(); j++) 
					dup.push_back(tmp[j]);
			}
			else {
				marbleBombed[val] += tmp.size();
				bombed = true;
			}
			tmp.clear();
			tmp.push_back(mv);
			val = mv;
		}
		else	tmp.push_back(mv);
	}
	if (tmp.size() < 4) {
		for (int j = 0; j < tmp.size(); j++)
			dup.push_back(tmp[j]);
	}
	else {
		marbleBombed[val] += tmp.size();
		bombed = true;
	}

	marble = dup;
}

void getTight() {
	marble.clear();
	bombed = false;
	for (int i = 1; i < num*num; i++) {
		int cx = v[i].x;
		int cy = v[i].y;
		int val = arr[cy][cx];
		if (val == 0) continue;
		marble.push_back(val);
	}
}

void changeMarble() {
	vector<int> dup, tmp;
	int val = -1;
	int cnt = 0;
	for (int i = 0; i < marble.size(); i++) {
		int mv = marble[i];
		if (mv == 0) break;
		if (val != mv) {
			if (cnt) {
				dup.push_back(cnt);
				dup.push_back(val);
			}
			val = mv;
			cnt = 1;
		}
		else
			cnt++;
	}
	if (cnt) {
		dup.push_back(cnt);
		dup.push_back(val);
	}
	marble = dup;
}

void setMarble2Arr() {
	while (marble.size() < num*num - 1) {
		marble.push_back(0);
	}
	int idx = 1;
	for (int i = 0; i < num*num - 1; i++) {
		int tx = v[idx].x;
		int ty = v[idx].y;
		arr[ty][tx] = marble[i];
		idx++;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num >> m;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			cin >> arr[i][j];
	sx = num / 2;
	sy = num / 2;
	init();

	while (m--) {
		cin >> dir >> s;
		dir--;
		blizard();
		while (1) {
			getTight();
			bombContinMarble();
			setMarble2Arr();
			if (!bombed) break;
		}
		changeMarble();
		setMarble2Arr();
	}
	cal();
	cout << answer;
	return 0;
}