[백준/BOJ] 백준 18500번 : 미네랄 2

www.acmicpc.net/problem/18500

18500번: 미네랄 2

제일 아래쪽에 모두 미네랄이 있다고 생각하고 문제를 해결했다. 이유는, 공중에 뜬 클러스터를 확인하기 위해, 바닥에 붙어 있는 클러스터를 체크했는데, 이때 제일 아래쪽(모두 미네랄이 있다고 생각한 곳)에서 탐색을 진행해서 바닥에 붙어 있는 클러스터들을 체크했기 때문이다.

 

코드

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

int r, c;
int n;
vector<string> board;
vector<int> stick;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

void Down_check(pair<int, int> here, vector<vector<int>>& check)
{
	check[here.first][here.second] = 1;

	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' && check[there.first][there.second] == 0)
		{
			Down_check(there, check);
		}
	}
}

//start위치가 속한 클러스터의 미네랄들을 반환한다
vector<pair<int, int>> Air(pair<int, int> start)
{
	vector<vector<int>> discovered(r, vector<int>(c, 0));
	queue<pair<int, int>> q;
	vector<pair<int, int>> ret;

	discovered[start.first][start.second] = 1;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		board[here.first][here.second] = '.';
		q.pop();

		ret.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);
			}
		}
	}

	return ret;

}

void Down()
{
	vector<vector<int>> check(r + 1, vector<int>(c, 0));

	//바닥과 붙어 있는 클러스터는 모두 체크한다
	Down_check(make_pair(r, 0), check);


	vector<pair<int, int>> air;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			//공중에 떠있는 클러스터를 만났을 경우
			if (board[i][j] == 'x' && check[i][j] == 0)
			{
				air = Air(make_pair(i, j));
				break;
			}
		}

		if (air.size() != 0)
			break;
	}

	//공중에 뜬 클러스터가 있을때
	if (air.size() != 0)
	{

		while (1)
		{
			bool meet = false; //더이상 내려가면 다른것과 만나는지 체크
			for (int i = 0; i < air.size(); i++)
			{
				if (board[air[i].first + 1][air[i].second] == 'x')
				{
					meet = true;
					break;
				}
			}

			if (meet == true)
			{
				break;
			}

			else
			{
				for (int i = 0; i < air.size(); i++)
					air[i].first++;
			}
		}

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

}

void Go_stick(int row, int turn)
{
	//왼쪽에서 던질때
	if (turn == 0)
	{
		for (int j = 0; j < c; j++)
		{
			if (board[row][j] == 'x')
			{
				board[row][j] = '.';
				break;
			}
		}
	}

	//오른쪽에서 던질때
	else
	{
		for (int j = c - 1; j >= 0; j--)
		{
			if (board[row][j] == 'x')
			{
				board[row][j] = '.';
				break;
			}
		}
	}
}

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

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	string down = "";
	for (int i = 0; i < c; i++)
		down += 'x';

	//제일 아래쪽에 모두 미네랄이 있다고 가정한다(바닥에 붙어 있는 클러스터를 확인하기 위해 사용한다)
	board.push_back(down);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		stick.push_back(input);
	}

	for (int i = 0; i < stick.size(); i++)
	{
		int height = stick[i];
		int row = r - height;
		int turn = i % 2;

		Go_stick(row, turn);
		Down();
	}

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

	return 0;
}