[백준/BOJ] 백준 2573번 : 빙산

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

2573번: 빙산

해당 연도의 빙하들이 다음 연도에 어떻게 될지를 구해놓고 다음 연도에도 빙하로 남아있는 것은 큐에 넣는다. 그리고 해당 연도가 끝났으면 빙하가 어떻게 될지 저장해 놓은 것으로 빙하를 업데이트한다. 이렇게 진행을 하며 빙하가 두 덩어리 이상으로 분리되는 때를 구한다

 

코드

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

int n, m;
int board[300][300];
int visited[300][300];
int dx_dy[4][2] = { {0,-1}, {-1,0}, {0,1}, {1,0} };

void checkIce(pair<int, int> here)
{
	visited[here.first][here.second] = 1;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

		if (there.first < n && there.first >= 0 && there.second < m && there.second >= 0 && board[there.first][there.second] > 0 && visited[there.first][there.second] == 0)
		{
			checkIce(there);
		}
	}
}

//빙산이 몇덩어리로 되어 있는지 dfs를 이용해 확인한다
int checkDivided()
{
	memset(visited, 0, sizeof(visited));

	int num = 0;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] > 0 && visited[i][j] == 0)
			{
				num++;

				checkIce(make_pair(i, j));
			}
		}

	return num;
}

int Solve(vector<pair<int, int>> ice)
{
	int cnt = 0;
	queue<pair<int, int>> q;
	vector<pair<pair<int, int>, int>> change;
	int q_size;
	int divided_num;

	for (int i = 0; i < ice.size(); i++)
	{
		q.push(ice[i]);
	}

	while (!q.empty())
	{
		//빙산이 몇덩어리로 되어 있는지 구한다
		divided_num = checkDivided();

		if (divided_num >= 2)
			return cnt;

		cnt++; //시간 증가

		q_size = q.size();

		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> here = q.front();
			q.pop();

			int here_ice = board[here.first][here.second];
			int water_num = 0;

			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

				//접해있는 바닷물의 개수를 센다
				if (there.first < n && there.first >= 0 && there.second < m && there.second >= 0 && board[there.first][there.second] == 0)
				{
					water_num++;
				}
			}

			here_ice -= water_num;

			if (here_ice < 0) //빙산의 높이는 0보다 줄어들지 않는다
				here_ice = 0;

			//아직 빙산이 남아있다면 다음 년도에 진행할것 이므로 큐에 넣는다
			if (here_ice > 0)
				q.push(make_pair(here.first, here.second));

			//해당 년도가 끝나면 바꿀 빙산의 위치와 높이를 저장한다
			change.push_back(make_pair(here, here_ice));
		}

		//해당 년도가 끝났을때 빙산의 높이를 바꿔준다
		for (int i = 0; i < change.size(); i++)
		{
			board[change[i].first.first][change[i].first.second] = change[i].second;
		}
		change.clear();
	}

	return 0;
}

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

	int temp;
	vector<pair<int, int>> ice;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> temp;
			board[i][j] = temp;

			if (temp != 0) //빙산의 위치를 저장한다
				ice.push_back(make_pair(i, j));
		}

	cout << Solve(ice);

	return 0;
}