[백준 2933] 미네랄

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

2933번: 미네랄

 

요구사항

게임이 끝난 후 미네랄의 모양 찾기

 

풀이

전체 과정

1. 맞춘 미네랄 삭제

2. 맞춘 미네랄 기준으로 클러스트 구하기(bfs, dfs)

3. 클러스트 추락하기(구현)

클러스트의 모양은 바뀌지 않으니깐 전체를 1칸씩 내려보고 내려진다면 down 아니라면 현재 위치에 클러스트를 위치시킨다.

 

차근 차근 조건에 맞추어 구현

 

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;

int n, m;
int r;
char map[110][110];
int visit[101][101];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
void bfs(int r, int c) {
//	cout << "B" << endl;
	memset(visit, 0, sizeof(visit));
	visit[r][c] = 1;
	map[r][c] = '.';
	vector<pair<int, int>> v;
	queue<pair<int, int>> q;
	v.push_back({ r,c });
	q.push({ r,c });
	//크러스터 구하고
	while (!q.empty()) {
		//cout << "C" << endl;
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = x + dr[i];
			int nc = y + dc[i];
			if (nr <= 0 || nc <= 0 || nr > n || nc > m) continue;
			if (visit[nr][nc] == 0 && map[nr][nc] == 'x') {
				visit[nr][nc] = 1;
				map[nr][nc] = '.';
				q.push({ nr,nc });
				v.push_back({ nr,nc });
			}
		}
	}

	//크러스터 하나씩 다운해보기
	int flag = 0;
	while (true) {
		vector<pair<int, int>> nv;
		for (int i = 0; i < v.size(); i++) {
			int x = v.at(i).first;
			int y = v.at(i).second;
			int nx = x + 1;
			nv.push_back({ nx,y });
			//바닥에 도착
			if (nx > n)
				flag = 1;
			//다른 크러스트 만남
			if (map[nx][y] == 'x') {
				flag = 1;
			}
		}
		if (flag == 1) {
			for (int i = 0; i < v.size(); i++) {
				int x = v.at(i).first;
				int y = v.at(i).second;
				map[x][y] = 'x';
			}
			break;
		}
		else {
			v.clear();
			v = nv;
		}
	}

}
void __throw(int sel,int num) {
	memset(visit, 0, sizeof(visit));
	if (sel % 2 == 0) {
		num = n - num + 1;
		for (int i = 1; i <= m; i++) {
			if (map[num][i] == 'x') {
				map[num][i] = '.';
				for (int j = 0; j < 4; j++) {
					int nx = num + dr[j];
					int ny = i + dc[j];
					if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
					if (map[nx][ny] == 'x' && visit[nx][ny]==0) {
						
						bfs(nx, ny);
					}
				}
				break;
			}
		}
	}
	else {
		num = n - num + 1;
		for (int i = m; i >= 1; i--) {
			if (map[num][i] == 'x') {
				map[num][i] = '.';
				for (int j = 0; j < 4; j++) {
					int nx = num + dr[j];
					int ny = i + dc[j];
					if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;
					if (map[nx][ny] == 'x' && visit[nx][ny] == 0) {
						bfs(nx, ny);
					}
				}
				break;
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &map[i][j]);
		}
	}

	scanf("%d", &r);
	for (int i = 0; i < r; i++) {
		int num;
		scanf("%d", &num);
		__throw(i,num);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			printf("%c", map[i][j]);
		}
		printf("\n");
	}
	
}