(BOJ) 2933 미네랄

문제: https://www.acmicpc.net/problem/2933

 

 

문제 설명:

1.  막대를 [왼쪽->오른쪽] [오른쪽->왼쪽] 방향을 바꿔가며 던진다

2. 막대가 미네랄(x)를 만나면 그 미네랄은 파괴되고 막대는 멈춘다  ( 'x' -> '.' )

2. 창에 맞아 x가 .으로 바뀌었을 때, 상하좌우로 열결된 미네랄(x)의 덩어리(상하좌우로 인접한 미네랄들)가 공중에 떠 있으면(바닥에 붙은 x와 연결되지 않았으면) 그 미네랄을 바닥 혹은 다른 x 위에 접하도록 내린다

 

 

문제 풀이:

1. 창에 맞은 x를 .로 만들기

2. bfs를 돌려서 현재 클러스터(덩어리)가 공중에 떠 있는지 확인

3. 만약 떠 있다면, 그 덩어리를 한 칸씩 전부 내려보고 밑에 닿는 것이 있으면 멈추고 아니면 한 칸 더 내리고 ... (반복)

 

 

소스 코드:

typedef pair<int, int> P;
int n, m, k;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
char arr[101][101];
bool visit[101][101], visit2[101][101];
bool change;
void func(P f) {
	queue <P> q;
	vector<P> v;

	visit[f.first][f.second] = true;
	q.push(f);
	v.push_back(f);

	bool nochange = false;
	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = curx + dx[i];
			int y = cury + dy[i];
			if (x < 0 || x >= n || y < 0 || y >= m || visit[x][y] || arr[x][y] == '.') continue;
			if (x == n - 1) nochange = true;
			visit[x][y] = true;
			q.push({ x,y });
			v.push_back({ x,y });
		}
	}
	if (nochange) return;
	bool chk = true;

	sort(v.begin(), v.end(), greater<>());
	memset(visit, false, sizeof(visit));
	while (chk) {
		for (int i = 0; i < v.size(); i++) {
			int x = v[i].first;
			int y = v[i].second;
			v[i].first++;
			arr[x + 1][y] = arr[x][y];
			arr[x][y] = '.';
			visit[x + 1][y] = true;
			if (x + 2 == n || (!visit[x + 2][y] && arr[x + 2][y] == 'x')) {
				chk = false;
			}
		}
	}
	change = true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		a = n - a;
		P tmp = make_pair(-1, -1);
		if (i % 2) {
			for (int j = m - 1; j >= 0; j--) {
				if (arr[a][j] == 'x') {
					arr[a][j] = '.';
					break;
				}
			}
		}
		else {
			for (int j = 0; j < m; j++) {
				if (arr[a][j] == 'x') {
					arr[a][j] = '.';
					break;
				}
			}
		}
		change = false;
		memset(visit, false, sizeof(visit));
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 'x' && !visit[i][j]) {
					func(make_pair(i, j));
					if (change) break;
				}
			}
			if (change) break;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << arr[i][j];
		}
		cout << '\n';
	}
	return 0;
}