[백준/BOJ] 백준 2933번 : 미네랄

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

2933번: 미네랄

떠있는 클러스터가 있는지 확인하는 방법은 board 하단에 가상의 미네랄을 한 줄 넣고, 가상의 미네랄에서 탐색을 진행해서 탐색한 미네랄의 개수가 전체 미네랄의 개수(가상 미네랄의 개수 포함)와 다르면 떠있는 클러스터가 있다고 판단하였다. 그리고 공중에 떠있는 클러스터가 얼마큼 떨어져야 될지는 그 클러스터에 속한 미네랄을 밑으로 내렸을 때 언제 다른 클러스터에 닿는지(가상 미네랄 포함)를 파악해 가장 작은 값만큼 밑으로 내린다.

 

코드

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

int r, c;
int n;
vector<string> board;
vector<int> stick;
int discovered[101][100];
int mineral_num = 0;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
vector<pair<int, int>> isolated_c;
int down_height;

void Print()
{
	for (int i = 0; i < r; i++)
	{
		cout << board[i] << "\n";
	}
}

void Pre()
{
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 100; j++)
			discovered[i][j] = 0;
	down_height = 987654321;
	isolated_c.clear();
}

void isolated_cCheck(pair<int, int> start)
{
	discovered[start.first][start.second] = 1; //공중에 떠있는 미네랄 체크는 1로 한다

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		isolated_c.push_back(here); //공중에 떠있는 클러스터의 미네랄 저장

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first <= r && there.second >= 0 && there.second < c && board[there.first][there.second] == 'x' && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}

	//얼만큼 떨어져야 될지 정한다
	for (int i = 0; i < isolated_c.size(); i++)
	{
		pair<int, int>isolated_m = isolated_c[i];
		int isolated_m_height = 0;

		for (int j = isolated_m.first + 1; j <= r; j++)
		{
			//바닥에 있는 미네랄을(가상미네랄 포함) 발견 했을때
			if (discovered[j][isolated_m.second] == -1)
				break;

			isolated_m_height++;
		}

		down_height = min(down_height, isolated_m_height);
	}
}

//공중에 떠있는 클러스터를 찾는다
void isolated_cFind()
{
	for (int i = 0; i <= r; i++)
		for (int j = 0; j < c; j++)
		{
			if (board[i][j] == 'x' && discovered[i][j] == 0)
				isolated_cCheck(make_pair(i, j)); //해당 클러스터의 미네랄을 체크한다
		}
}

//공중에 떠있는 클러스터를 내린다
void Down()
{
	vector<pair<int, int>> changed;

	for (int i = 0; i < isolated_c.size(); i++)
	{
		pair<int, int>isolated_mineral = isolated_c[i];
		changed.push_back(make_pair(isolated_mineral.first + down_height, isolated_mineral.second));
		board[isolated_mineral.first][isolated_mineral.second] = '.';
	}

	for (int i = 0; i < changed.size(); i++)
	{
		board[changed[i].first][changed[i].second] = 'x';
	}
}

bool lowCheck()
{
	int low_mineral_num = 0;
	pair<int, int> start = make_pair(r, 0); //밑에서 부터(가상의 미네랄부터) 탐색을 진행한다

	discovered[start.first][start.second] = -1; //발견은 -1로 표시
	
	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		low_mineral_num++;

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first <= r && there.second >= 0 && there.second < c && board[there.first][there.second] == 'x' && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = -1;
				q.push(there);
			}
		}
	}

	//밑에서 부터 확인한 미네랄과 전체 미네랄의 개수가 같을때 즉, 공중에 떠있는것이 없을때
	if (low_mineral_num == mineral_num)
		return true;

	return false;
}

void Throw(int height, int human)
{
	if (human == 0) //창영이가 던질때
	{
		for (int i = 0; i < c; i++)
		{
			if (board[r - height][i] == 'x')
			{
				board[r - height][i] = '.';
				mineral_num--; //미네랄 감소
				break;
			}
		}
	}

	else //상근이가 던질때
	{
		for (int i = c - 1; i >= 0; i--)
		{
			if (board[r - height][i] == 'x')
			{
				board[r - height][i] = '.';
				mineral_num--; //미네랄 감소
				break;
			}
		}
	}
}

void Solve()
{
	for (int i = 0; i < stick.size(); i++)
	{
		Throw(stick[i], i % 2);

		Pre();
		if (!lowCheck())
		{
			isolated_cFind();
			Down();
		}
	}

	Print();
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string input_s;
	int input_i;

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		cin >> input_s;
		for (int j = 0; j < c; j++)
		{
			//미네랄의 개수를 센다
			if (input_s[j] == 'x')
				mineral_num++;
		}
		board.push_back(input_s);
	}

	//마지막줄에 가상의 미네랄 한줄을 넣는다(나중에 떠있는 클러스터를 확인하기 위해)
	input_s = "";
	for (int i = 0; i < c; i++)
	{
		input_s += "x";
		mineral_num++;//미네랄의 개수를 추가
	}
	board.push_back(input_s);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input_i;
		stick.push_back(input_i);
	}

	Solve();

	return 0;
}