미네랄 (feat. 백준, 2933번)

미네랄
https://www.acmicpc.net/problem/2933

2933번: 미네랄

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int R, C, N, H, dx[4], dy[4];
char arr[101][101];
bool visit[101][101];
vector<vector<pair<int, int>>> clusters;	// (클러스터)
inline int left_stick(register int height) {
	register int ret = -1;
	for (register int c = 1; c <= C; ++c)
		if (arr[height][c] == 'x') {
			ret = c;
			break;
		}
	return ret;
}
inline int right_stick(register int height) {
	register int ret = -1;
	for(register int c = C; c >= 1; --c)
		if (arr[height][c] == 'x') {
			ret = c;
			break;
		}
	return ret;
}
void get_clusters(register int x, register int y) {
	if (visit[x][y])
		return;
	visit[x][y] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	vector<pair<int, int>> cluster;
	cluster.push_back(q.front());
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && arr[nx][ny] == 'x' && !visit[nx][ny])
				visit[nx][ny] = true, q.push(make_pair(nx, ny)), cluster.push_back(make_pair(nx, ny));
		}
	}
	sort(cluster.begin(), cluster.end());
	clusters.push_back(cluster);
}
void move_clusters(vector<pair<int, int>>& cluster) {
	register int x, y;
	while (1) {
		bool check = true;
		for (auto iter = cluster.begin(); iter != cluster.end(); ++iter) {
			x = iter->first, y = iter->second;
			if (x == 1)
				return;
			arr[x][y] = 'y';				// 마킹
			if (arr[x - 1][y] == 'x') {
				check = false;
				break;
			}
		}
		if (check)
			for (auto iter = cluster.begin(); iter != cluster.end(); ++iter) {
				x = iter->first, y = iter->second;
				arr[x][y] = '.', arr[x - 1][y] = 'x';
				iter->first = x - 1;
			}
		else {
			for (register int r = 1, c; r <= R; ++r)
				for (c = 1; c <= C; ++c)
					if (arr[r][c] == 'y')
						arr[r][c] = '.';
			for (auto iter = cluster.begin(); iter != cluster.end(); ++iter) {
				x = iter->first, y = iter->second;
				arr[x][y] = 'x';
			}
			break;
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> R >> C;
	for (register int r = 0, c; r < R; ++r)
		for (c = 1; c <= C; ++c)
			cin >> arr[R - r][c];
	cin >> N;
	bool is_left = false;
	for (register int n = 1, mineral; n <= N; ++n) {
		cin >> H;
		if (is_left = !is_left)
			mineral = left_stick(H);		// 왼쪽 막대기인 경우 첫 미네랄의 열
		else
			mineral = right_stick(H);		// 오른쪽 막대기인 경우 첫 미네랄의 열
		if (mineral > 0) {
			arr[H][mineral] = '.';			// 미네랄 터트림
			memset(visit, false, sizeof(visit));
			if (is_left) {
				if (mineral + 1 <= C && arr[H][mineral + 1] == 'x')		// 터진 미네랄의 오른쪽과 연결된 클러스터묶음 찾기
					get_clusters(H, mineral + 1);
				if (H + 1 <= R && arr[H + 1][mineral] == 'x')			// 터진 미네랄의 위쪽과 연결된 클러스터묶음 찾기
					get_clusters(H + 1, mineral);
				if (H - 1 >= 1 && arr[H - 1][mineral] == 'x')			// 터진 미네랄의 아래쪽과 연결된 클러스터묶음 찾기
					get_clusters(H - 1, mineral);
			}
			else {
				if (mineral - 1 >= 1 && arr[H][mineral - 1] == 'x')		// 터진 미네랄의 왼쪽과 연결된 클러스터묶음 찾기
					get_clusters(H, mineral - 1);
				if (H + 1 <= R && arr[H + 1][mineral] == 'x')			// 터진 미네랄의 위쪽과 연결된 클러스터묶음 찾기
					get_clusters(H + 1, mineral);
				if (H - 1 >= 1 && arr[H - 1][mineral] == 'x')			// 터진 미네랄의 아래쪽과 연결된 클러스터묶음 찾기
					get_clusters(H - 1, mineral);
			}
			for (auto& cluster : clusters)
				move_clusters(cluster);				// 클러스터들을 아래로 떨어트림
			clusters.clear();
		}
	}
	for (register int r = R, c; r >= 1; --r) {
		for (c = 1; c <= C; ++c)
			cout << arr[r][c];
		cout << "\n";
	}
	return 0;
}
// *&)*@*

1. 왼쪽 또는 오른쪽으로부터 막대기가 날라올때 처음으로 만나는 미네랄 ('x') 가 터지게 됩니다.
2. 위 미네랄 기준 상, 하. 그리고 왼쪽에서 날라오는 막대기라면 우, 오른쪽에서 날라오는 막대기라면 좌 에 대해서 클러스터로 묶이는지 bfs를 진행합니다.
3. 2번에 의해 구해진 클러스터들 (1개~3개일 수 있습니다.) 에 대해서 중력을 작용시켜 아래로 떨어트립니다.
   단, 클러스터 뭉치가 한칸씩 내려간다면 그 구간에는 미네랄도 없고 바닥도 아니어야 합니다.