[백준OJ] 2933번 미네랄

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

2933번: 미네랄

---

 

풀이

1. 맵을 입력받는다.

 

2. 입력받은 뒤, 좌 우 좌 우 순서대로 부술 라인을 입력받는다.

 

3. 해당라인, 해당 방향에서 처음 만나는 미네랄을 부순 뒤, 상/하/좌/우 를 BFS로 탐색을 하면서, 바닥과 연결되어있지않은(중력에의해 떨어져야 하는 미네랄 덩어리)를 찾아준다. 문제에서 2개의 덩어리가 동시에 떨어지지 않는다는 조건이 있으므로, 하나의 덩어리만 찾아질것이다.

 

4. 만약 3번에서 중력에의해 떨어져야하는 미네랄 덩어리가 없다면, 바로 다음 라인을 부숴주면된다.

 

5. 미네랄 덩어리가 있다면, 미네랄 덩어리중 한 부분이 바닥에 닿거나, 다른 미네랄 덩어리에 닿기전까지 아래로 내려준다.

이때 앞에 9개의 미네랄은 충돌이 생기지 않았지만, 마지막 미네랄이 다른 미네랄과 충돌이 생긴다면, 다시 되돌려줘야하므로, 임시배열을 선언해서, 임시배열위에서 한칸씩 내려본 뒤, 충돌이 없다면 오리지날 배열에 복사하는 식으로 했다.

또, 아래쪽 미네랄부터 먼저 떨어트려주어야하므로, 미네랄을 아래쪽미네랄이 우선순위를 갖도록 정렬해주었다.

 

6. 위의 로직을 반복한 뒤, 출력해준다.

 

반응형

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef pair<int, int> pii;

char maze[101][101];
int mv[4][2] = { {-1,0},{0,1},{0,-1},{1,0} };
int r, c, n, line;

bool isIn(int x, int y) {
	return 0 <= x && x < r && 0 <= y && y < c;
}

bool isBottom(int x) {
	return x == r - 1;
}

//미네랄 정렬기준을 더 아래쪽에 있는것부터 정렬
bool compare(pii a, pii b) {
	return a.first > b.first;
}

void down(int a, int b) {
	vector<pii> mineral;
	maze[a][b] = '.';
	//떠있는 미네랄을 찾기위함.
	for (int i = 0; i < 4; i++) {
		int nx = a + mv[i][0];
		int ny = b + mv[i][1];
		if (isIn(nx, ny) && maze[nx][ny] == 'x') {
			bool flag = true;
			bool visited[101][101] = { 0 };
			queue<pii> q;
			q.push({ nx,ny });
			mineral.push_back({ nx,ny });
			visited[nx][ny] = true;
			//미네랄 수집
			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				if (isBottom(x)) {
					flag = false;
					break;
				}
				for (int i = 0; i < 4; i++) {
					int nx = x + mv[i][0];
					int ny = y + mv[i][1];

					if (isIn(nx, ny) && maze[nx][ny] == 'x' && !visited[nx][ny]) {
						q.push({ nx,ny });
						mineral.push_back({ nx,ny });
						visited[nx][ny] = true;
					}
				}
			}
			if (flag) break;
			else mineral.clear();
		}
	}
	if (mineral.empty()) return; //미네랄이 없으면 return;

	//아래쪽에있는미네랄을 우선순위로 정렬
	sort(mineral.begin(), mineral.end(), compare);

	//미네랄 이동전 복사
	char tempMaze[101][101];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			tempMaze[i][j] = maze[i][j];
		}
	}
	//충돌까지 미네랄 이동
	while (true) {
		bool crush = false;
		for (int i = 0; i < mineral.size(); i++) {
			int x = mineral[i].first+1;//한칸 아래로
			int y = mineral[i].second;

			if (isIn(x, y) && tempMaze[x][y] == '.') {
				tempMaze[x][y] = 'x';
				tempMaze[x - 1][y] = '.';
				mineral[i].first += 1;
			}
			else {
				crush = true;
				break;
			}
		}
		if (crush) return;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				maze[i][j] = tempMaze[i][j];
			}
		}
	}
	
}

void hitMineral(bool left,int l) {
	l = r - l;//위아래 바꾸기위해
	if (left) {
		for (int i = 0; i < c; i++) {
			if (maze[l][i] == 'x') {
				down(l, i);
				return;
			}
		}
	}
	else {
		for (int i = c-1; i >=0; i--) {
			if (maze[l][i] == 'x') {
				down(l, i);
				return;
			}
		}
	}
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> maze[i][j];
		}
	}

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> line;
		hitMineral(i%2,line);
	}
	
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maze[i][j];
		}
		cout << "\n";
	}
	return 0;
}