[백준] 2933. 미네랄 ( C / C++)

1. 문제 링크

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

2933번: 미네랄

#include <cstdio>
#include <queue>
using namespace std;

struct COORD {
	int y, x;
};
char map[100][100];
int group[100][100];
int r, c, n;
int groupnum = 1;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

bool grouping_check(void)
{
	//grouping and check
	bool visited[100][100] = { false, };
	queue<COORD> q;
	
	groupnum = 1;
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			group[i][j] = 0;

	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			if (map[i][j] == 'x' && !visited[i][j])
			{
				bool check = false;
				COORD start;
				start.y = i, start.x = j;
				visited[i][j] = true;
				q.push(start);
				while (!q.empty())
				{
					COORD cur = q.front(); q.pop();
					group[cur.y][cur.x] = groupnum;
					if (cur.y == r - 1)
					{
						//if the block is on the land
						check = true;
					}
					for (int dir = 0; dir < 4; dir++)
					{
						COORD next;
						next.y = cur.y + dy[dir];
						next.x = cur.x + dx[dir];

						if (next.y < 0 || next.x < 0 || next.x >= c || next.y >= r || map[next.y][next.x] == '.')
							continue;
						if (visited[next.y][next.x] == false)
						{
							visited[next.y][next.x] = true;
							q.push(next);
						}
					}
				}
				if (!check)
					return false;

				groupnum++;
			}
		}
	}
	return true;
}
void shoot_arrow(int row, int dir)
{
	//dir -> 1 : left , ->2 : right
	if (dir == 1){
		for (int j = 0; j < c; j++)
			if (map[row][j] == 'x') {
				map[row][j] = '.';
				return;
			}	
	}
	else if (dir == 2){
		for (int j = c - 1; j >= 0; j--)
			if (map[row][j] == 'x'){
				map[row][j] = '.';
				return;
			}
	}
	return;
}
bool drop_mineral(void)
{
	//check
	for (int j = 0; j < c; j++)
	{
		for (int i = r - 1; i >= 0; i--)
		{
			if (group[i][j] == groupnum)
			{
				if (i == r - 1)	return false;
				if (group[i+1][j] != group[i][j] && map[i + 1][j] == 'x')	return false;
			}
		}
	}

	//and go
	for (int j = 0; j < c; j++)
	{
		for (int i = r - 1; i >= 0; i--)
		{
			if (group[i][j] == groupnum)
			{
				map[i + 1][j] = map[i][j];
				group[i + 1][j] = group[i][j];
				map[i][j] = '.';
			}
		}
	}
	return true;
}
int main(void)
{
	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; i++)
		scanf("%s", map[i]);
	scanf("%d", &n);
	for (int k = 1; k <= n; k++)
	{
		int row;
		scanf("%d", &row);
		
		//throw
		if (k % 2 == 1)
			shoot_arrow(r-row, 1);
		else
			shoot_arrow(r-row, 2);
		
		//check .. if it should be dropped, 
		if (!grouping_check())
			while (drop_mineral());
		
	}
	//print
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++)
		{
			printf("%c", map[i][j]);
		}
		printf("\n");
	}
	return 0;

}

 

지적, 댓글 언제나 환영입니다~