2573번: 빙산

Code

제출 날짜

2021/03/31

메모리

2820 KB

시간

96 ms

#include <iostream>
#include <cstring>
#include <queue>

int N, M;
int g_map[302][302];
int tmp[302][302];
bool visited[302][302];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};
std::queue<std::pair<int, int> >q;
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> M;
	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < M ; j++)
			std::cin >> g_map[i][j];
}

void bfs(int i, int j)
{
	int y,x, nx,ny;
	visited[i][j] = 1;
	q.push({i, j});
	while(!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int k = 0 ; k < 4 ; k++)
		{
			ny = y + dy[k];
			nx = x + dx[k];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx] || !g_map[ny][nx])
				continue;
			visited[ny][nx] = 1;
			q.push({ny, nx});
		}
	}
}

int cal_ice() // 빙산 덩어리 수 계산
{
	int ret = 0;

	q = std::queue<std::pair<int, int> >();
	memset(visited, 0, sizeof(visited));
	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < M ; j++)
		{
			if (visited[i][j] || !g_map[i][j])
				continue;
			ret++;
			bfs(i, j);
		}
	return (ret);
}

int cal_surround_water(int y, int x) // 바닷물이 얼마나 인접해 있는지 계산
{
	int nx, ny;
	int ret = 0;

	for (int k = 0 ; k < 4 ; k++)
	{
		ny = y + dy[k];
		nx = x + dx[k];
		if (ny < 0 || ny >= N || nx < 0 || nx >= M || g_map[ny][nx])
			continue;
		ret++;
	}
	return (ret);
}

bool no_ice() // 빙산이 있는지 확인
{
	for (int i = 0 ;i < N ; i++)
		for (int j = 0 ; j < M ; j++)
			if (g_map[i][j])
				return (0);
	ans = 0;
	return (1);
}

void solve()
{
	int surrounded_water;

	while(cal_ice() < 2 && !no_ice())
	{
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < M ; j++)
			{
				if (!g_map[i][j])
				{
					tmp[i][j] = 0;
					continue;
				}
				surrounded_water = cal_surround_water(i, j);
				tmp[i][j] = g_map[i][j] - surrounded_water;
				if (tmp[i][j] < 0)
					tmp[i][j] = 0;
			}
		std::memcpy(g_map, tmp, sizeof(tmp));
		ans++;
	}
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}