[백준/BOJ] 백준 2933번 : 미네랄
2020. 8. 26. 08:28ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 17142번 : 연구소 3 (0) | 2020.08.26 |
---|---|
[백준/BOJ] 백준 17141번 : 연구소 2 (0) | 2020.08.26 |
[백준/BOJ] 백준 16137번 : 견우와 직녀 (0) | 2020.08.26 |
[백준/BOJ] 백준 14621번 : 나만 안되는 연애 (0) | 2020.08.26 |
[백준/BOJ] 백준 2887번 : 행성 터널 (0) | 2020.08.26 |