BOJ 2933 미네랄 / C++

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

2933번: 미네랄

 

백준 온라인저지 2933번 미네랄 문제입니다.

 

아이디어

막대기를 던질때마다 발생하는 클러스트가 중력에 의해 바닥에 닿을때까지의 처리가 중요해보이는 문제였습니다.

클러스트의 각 원소가 바닥에 있는 미네랄까지 닿는 가장 적은 이동거리를 구하여 이동시킨 후 다음 로직을 실행하는 과정으러 풀어냈습니다. 필요한 부분은 주석으로 설명되어 있다고 생각하지만 필요한 부분은 질문 부탁드립니다.

 

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

class point {
public:
	int y;
	int x;
	point(int a, int b) {
		y = a;
		x = b;
	}
};

char arr[101][101];
bool visited[101][101];
int r, c;
int n;
vector<int> nums;
vector<point> cluster;
int mx[4] = { 0,0,-1,1 };
int my[4] = { 1,-1,0,0 };




void input() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
		}
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		nums.push_back(k);
	}
}

//막대기 던지는 로직
void throwStick(int i) {
	if (i < 0) {
		i *= -1;
		for (int j = c - 1; j >= 0; j--) {
			if (arr[i][j] == 'x') {
				arr[i][j] = '.';
				break;
			}
		}
	}
	else{
		for (int j = 0; j < c; j++) {
			if (arr[i][j] == 'x') {
				arr[i][j] = '.';
				break;
			}
		}
	}
	
}

//땅에 붙은 미네랄 방문처리
void bfs(int a, int b) {
	queue<point>q;
	q.push(point(a, b));
	visited[a][b] = true;
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int y = p.y + my[i];
			int x = p.x + mx[i];
			if (y >= r || y < 0 || x >= c || x < 0) continue;
			if (arr[y][x] == '.') continue;
			if (visited[y][x]) continue;
			visited[y][x] = true;
			q.push(point(y, x));
		}
	}

}

//미네랄 아래로 움직일 수 있는 최대 칸수 반환
int findMoveCnt() {
	int cnt = 987654321;
	for (int i = 0; i < cluster.size(); i++) {
		int moveCnt = 0;
		point p = cluster[i];
		for (int j = p.y+1; j < r; j++) {
			//클러스터 미네랄과 닿을시(클러스터인 미네랄과 닿는다는 것은 moveCnt가 의미 없다는 것
			if (arr[j][p.x] == 'x' && !visited[j][p.x]) {
				moveCnt = 0;
				break;
			}

			//바닥에 닿은 미네랄과 닿을시
			if (arr[j][p.x] == 'x' && visited[j][p.x]) break;
			moveCnt++;
		}
		if (moveCnt != 0)
			cnt = min(cnt, moveCnt);
	}
	return cnt;
}

//클러스터를 moveCnt만큼 아래로 이동시켜서 다시 그림
void redraw(int moveCnt) {
	for (auto iter : cluster) 
		arr[iter.y][iter.x] = '.';

	for (auto iter : cluster)
		arr[iter.y + moveCnt][iter.x] = 'x';
}

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


void solution() {
	for (int i = 0; i < nums.size(); i++) {
		//초기화
		cluster.clear();
		memset(visited, false, sizeof(visited));
		int h = r - nums[i];
		if (i % 2)
			h *= -1;
		//막대기 던지기
		throwStick(h);
		
		//땅에 붙은 미네랄 방문처리
		for (int i = 0; i < c; i++) {
			if(!visited[r-1][i])
				bfs(r-1, i);
		}

		//클러스터의 존재 확인
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (arr[i][j] == 'x' && !visited[i][j])
					cluster.push_back(point(i, j));
			}
		}

		//클러스터가 없으면 pass
		if (cluster.size() == 0) continue;
		
		//몇칸 내려가야하는지 확인
		int moveCnt = findMoveCnt();

		//그림 다시그리기
		redraw(moveCnt);
	}
	print();
}

int main(void) {
	input();
	solution();
}