#2933 미네랄

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

2933번: 미네랄

 

문제에서 요구하는 사항을 구현하는 단순 구현 문제이다. 하지만 구현이 요소에 1.미네랄 깨기, 2. 그룹생성하기, 3.떠 있는 그룹 내리기 와 같이 요구사항이 조금 있어 정리를 하지 않고 무턱대고 구현을 했다가는 나중에 디버깅 오류 검출시  어떤부분에서 오류가 생겼는지 확인하기가 쉽지 않아진다. 그래서 알고리즘 순서를 다음과 같이 먼저 정해놓고 단계별로 디버깅을 하며 구현을 해나갔다.

 

알고리즘 순서

 

두 사람이 오른쪽 왼쪽 순서대로 창을 던진다.

 

1. 창을 던져 미네랄을 없앤다

2. 새롭게 그룹을 생성하고 '떠' 있으면 '내려준다.'

2-1. 내리는 과정 맨 밑바닥을 그룹 0or1로 추가해 타그룹의 미네랄(X)인 x,y좌표 비교해 그거리가 최소가 되는만큼 내려준다.

 

	// #b2933 미네랄
	#include <iostream>
	#include <cstring>
	#include <vector>
	#include <queue>
	using namespace std;
	int k;//막대를 던진 횟수
	int n, m;
	char arr[102][102];
	int visit[101][101];
	int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };
	int group_Count = 1;
	int MIN(int a, int b) {
	return a < b ? a : b;
	}
	typedef struct xy {
	int x, y;
	}xy;
	vector <xy> group[10001];
	queue<int>q;
	void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
	int nx = x + dir[i][0];
	int ny = y + dir[i][1];
	if (nx <= 0 || nx > n || ny <= 0 || ny > m)continue;
	if (visit[nx][ny])continue;
	if (arr[nx][ny] == '.')continue;
	visit[nx][ny] = group_Count;
	group[group_Count].push_back({ nx,ny });
	dfs(nx, ny);
	}
	}
	int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = n; i >= 1; i--) {
	for (int j = 1; j <= m; j++) {
	cin >> arr[i][j];
	}
	}
	for (int j = 1; j <= m; j++) {
	group[0].push_back({ 0,j });
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
	int x;
	cin >> x;
	q.push(x);
	}
	//simul
	int TIME = 0;
	while (!q.empty()) {//창 다 던질때까지
	int fx = q.front();
	int fy;
	int d;
	if (TIME % 2 == 0) {
	fy = 1, d = 1;
	}
	else {
	fy = m, d = -1;
	}
	q.pop();
	// 1. 창을 던져 미네랄을 없앤다
	while (true) {
	if (arr[fx][fy] == 'x') {
	arr[fx][fy] = '.';
	break;
	}
	fy += d;
	if (fy <= 0 || fy > m)break;
	}
	//cout << "fx " << fx << " fy " << fy << endl;
	// 2. 새롭게 그룹을 생성하고 '떠' 있으면 '내려준다.'
	// 2-1. 내리는 과정 맨 밑바닥을 그룹 0or1로 추가해 타그룹의 벽(X)인 x,y좌표 비교해
	// 그거리가 최소가 되는만큼 내려준다.
	//그룹핑
	group_Count = 1;
	memset(visit, 0, sizeof(visit));
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
	if (arr[i][j] == 'x'&&visit[i][j] == 0) {
	visit[i][j] = group_Count;
	group[group_Count].push_back({ i,j });
	dfs(i, j);
	group_Count++;
	}
	}
	}
	for (int i = 1; i < group_Count; i++) {//0은 내릴필요 없으니
	int minn = 1000;//내릴 값
	//cout << "group i " << i << endl;
	for (int j = 0; j < group_Count; j++) {
	if (i == j)continue;
	//cout << "group j " << j << endl;
	for (int ii = 0; ii < group[i].size(); ii++) {
	for (int jj = 0; jj < group[j].size(); jj++) {
	int fx = group[i][ii].x, fy = group[i][ii].y;
	int nx = group[j][jj].x, ny = group[j][jj].y;
	//내릴값이 0이 나와버리면 다음 i로 넘어가자.
	//내릴값이 0이 아니면 다끊고 맵 내리는 과정으로 넘어가면된다.
	//두개이상 클러스터 동시떨어질 일 없으므로
	if (fy == ny&&fx>nx) {//높이가 다르고 내릴것이 위에 있으면
	//cout << "fx " << fx << " fy " << fy << " nx " << nx<<" ny "<<ny<<" minn "<<minn << endl;
	minn = MIN(fx - nx, minn);
	}
	}
	}
	if (minn == 1)break;
	}
	//내린다.
	if (minn >= 2) {
	//cout << "i " << i << " min " << minn << endl;//
	for (int x = 1; x <= n; x++) {
	for (int y = 1; y <= m; y++) {
	if (visit[x][y] == i) {
	arr[x][y] = '.';
	arr[x - minn + 1][y] = 'x';
	}
	}
	}
	break;
	}
	}
	TIME++;
	for (int i = 1; i <group_Count; i++) {
	group[i].clear();
	}
	}
	for (int i = n; i >= 1; i--) {
	for (int j = 1; j <= m; j++) {
	cout << arr[i][j];
	}cout << endl;
	}
	}

view raw [BOJ]2933.cpp hosted with ❤ by GitHub