[백준] 골드4 : (2573) 빙산

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

 

시간마다 빙산을 녹이는 로직 실행 (상하좌우 0이 있으면 1씩 줄이기)

 

시간이 지난 후, 남아있는 아무 빙산 1개를 시작으로 BFS 실행

 

BFS로 탐색한 빙하의 수와 맵에 남아있는 빙하의 수가 일치하지 않으면, 시간 리턴 후 종료

맵에 빙하가 없으면 0 리턴 후 종료

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

int dy[]{ -1, 0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };
int N, M;

void AddTime(vector<vector<int>>& Map, queue<int>& qy, queue<int>& qx, queue<int>& qn, vector<vector<bool>>& Visit)
{
	queue<pair<int, int>> Remove;

	int Size = qy.size();
	for (int i = 0; i < Size; ++i)
	{
		int y = qy.front(), x = qx.front(), n = qn.front();
		qy.pop(), qx.pop(), qn.pop();

		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M || Map[ny][nx] > 0) continue;

			n--;
		}
		if (n > 0) qy.push(y), qx.push(x), qn.push(n);
		else Remove.push({ y, x });

	}

	while (!Remove.empty())
	{
		int y = Remove.front().first, x = Remove.front().second;
		Map[y][x] = 0, Visit[y][x] = false;
		Remove.pop();
	}
}

int Func(vector<vector<int>>& Map, int sy, int sx, vector<vector<bool>> Visit)
{
	int Ret = 1;

	Visit[sy][sx] = false;

	queue<int> qy, qx;
	qy.push(sy), qx.push(sx);

	while (!qy.empty())
	{
		int y = qy.front(), x = qx.front();
		qy.pop(), qx.pop();

		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dy[i], nx = x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M || !Visit[ny][nx]) continue;

			Ret++;
			Visit[ny][nx] = false;
			qy.push(ny), qx.push(nx);
		}
	}
	return Ret;
}

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

	int Time = 0;
	cin >> N >> M;

	// 맵 배열, 빙하의 높이 정보
	vector<vector<int>> Map(N, vector<int>(M));

	// 맵에 남아있는 빙하 정보
	vector<vector<bool>> Visit(N, vector<bool>(M, false));

	// 빙하 y축, x축, 높이
	queue<int> qy, qx, qn;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> Map[i][j];
			if (Map[i][j] != 0)
			{
				qy.push(i), qx.push(j), qn.push(Map[i][j]);
				Visit[i][j] = true;
			}
		}
	}

	while (true)
	{
		Time++;

		// 시간 보내기 로직 수행
		// 빙하 위치 기준 상하좌우에 0 개수만큼 높이 줄임
		AddTime(Map, qy, qx, qn, Visit);

		if (qy.empty()) break; // 남은 빙하가 없으면 종료

		// 빙하 하나를 기준으로 BFS 수행
		// BFS로 찾은 빙하의 수와 현재 남은 빙하의 수가 일치하지 않으면, 보낸 시간 반환
		if (Func(Map, qy.front(), qx.front(), Visit) != qy.size()) { cout << Time << "\n"; return 0; }
	}
	cout << 0 << "\n";
}