2933(구현)

첫인상

100X100 이차원 배열에 명령의 갯수도 100개 밖에 안돼서 시간은 여유롭다고 판단했고 미네랄이 부서졌을 때 분리 여부를 따지기 위해 bfs를 사용해야겠다 생각이 들었다

풀이

막대기를 던져서 미네랄이 부서질 때마다 바닥에 붙은 덩어리들을 판별하고 부서진 미네랄에 인접한 미네랄에 대해서 분리된 덩어리인지를 판별해주었다. 이후 분리된 덩어리가 떨어질 수 있는 최대 거리를 받아와서 떨어뜨렸다.

코드

#include<iostream>
#include<queue>
#define pii pair<int, int>
using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int r, c;
string map[105];
int visit[105][105];
queue<int> coms;

void input() {
	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		cin >> map[i];
	}

	int cnt;
	int tmp;

	cin >> cnt;

	for (int i = 0; i < cnt; i++) {
		cin >> tmp;
		coms.push(tmp);
	}
}

int leftToRight(int n) {
	for (int i = 0; i < c; i++) {
		if (map[n][i] == 'x') {
			map[n][i] = '.';
			return i;
		}
	}
	return -1;
}

int rightToLeft(int n) {
	for (int i = c - 1; i >= 0; i--) {
		if (map[n][i] == 'x') {
			map[n][i] = '.';
			return i;
		}
	}
	return -1;
}

void bfs(int x, int y, int n) {
	queue<pii> que;
	que.push({ x,y });
	visit[x][y] = n;
	
	while (!que.empty()) {
		x = que.front().first;
		y = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
				continue;
			}

			if (map[nx][ny] == 'x' && visit[nx][ny] == 0) {
				que.push({ nx,ny });
				visit[nx][ny] = n;
			}
		}
	}
}

int idx;
void check(int x, int y) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			visit[i][j] = 0;
		}
	}

	for (int i = 0; i < c; i++) {
		if (map[r - 1][i] == 'x' && visit[r - 1][i] == 0) {
			bfs(r - 1, i, 1);
		}
	}

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
			continue;
		}

		if (map[nx][ny] == 'x' && visit[nx][ny] == 0) {
			bfs(nx, ny, 2);
		}
	}
}

void down() {
	int min = 105;
	int cnt;

	for (int i = 0; i < c; i++) {
		cnt = 105;
		for (int j = 0; j < r; j++) {
			if(visit[j][i] == 2){
				cnt = 0;
			}
			else if (visit[j][i] == 0) {
				cnt += 1;
			}
			else if (visit[j][i] == 1) {
				if (cnt < min) {
					min = cnt;
					cnt = 105;
				}
			}
		}
		if (cnt < min) {
			min = cnt;
		}
	}

	for (int i = 0; i < c; i++) {
		for (int j = 0; j < r; j++) {
			if (visit[r - j - 1][i] == 2) {
				map[r - j - 1 + min][i] = 'x';
				map[r - j - 1][i] = '.';
			}
		}
	}
}

void print() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << map[i][j];
		}
		cout << "\n";
	}
}

void solve() {
	bool odd = true;

	while (!coms.empty()) {
		int com = coms.front();
		coms.pop();

		int tmp;
		if (odd) {
			odd = false;
			tmp = leftToRight(r - com);
		}
		else {
			odd = true;
			tmp = rightToLeft(r - com);
		}
		check(r - com, tmp);

		down();
	}
}

int main() {
	input();
	solve();
	print();
}