문제 풀이

빙산의 높이를 입력받을 배열(arr) 하나와 해당 빙산의 주변의 0의 개수를 저장해둘 배열(arr2)을 추가로 활용한다.

먼저 dfs를 돌아 dfs가 몇번에 나누어서 돌았는지(divide)를 체크해주고
dfs를 도는 동안 해당 빙산의 주변에 바다가 몇 방향이나 있는지 체크해주어 arr2에 저장해두고
dfs를 모두 돌았으면 아래와 같이 높이가 음수가 되지 않도록 녹여준다.

if (arr[i][j] - arr2[i][j] >= 0)
	arr[i][j] -= arr2[i][j];
else
	arr[i][j] = 0;

divide가 0이면 모두 녹아버렸다는 뜻으로 0을 출력해주고 종료한다.
그게 아니고 divide가 2이상이면 둘로 빙산이 둘 이상으로 나누어졌다는 뜻으로 year를 출력하고 종료한다.

문제 링크

boj/2573

소스코드

PS/2573.cpp

#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<memory.h>
using namespace std;

int n, m;
int arr[301][301];
int arr2[301][301];
bool visit[301][301];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void dfs(int x, int y);
int main() {

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	}
	int year = 0;
	while (1)
	{
		int divide = 0;
		memset(arr2, 0, sizeof(arr2));
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (visit[i][j] == 0 && arr[i][j] >= 1)
				{
					divide++;
					dfs(j, i);
				}
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (arr[i][j] - arr2[i][j] >= 0)
					arr[i][j] -= arr2[i][j];
				else
					arr[i][j] = 0;
			}
		}
		if (divide == 0)
		{
			cout << 0;
			return 0;
		}
		if (divide >= 2)
		{
			cout << year;
			return 0;
		}
		year++;
	}
}

void dfs(int x, int y)
{
	visit[y][x] = 1;
	int cnt = 0;
	
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && ny < n && nx < m && arr[ny][nx] == 0)
			cnt++;
	}
	arr2[y][x] = cnt;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx>=0 && ny>=0 && ny<n && nx< m && visit[ny][nx] == 0 && arr[ny][nx] != 0)
			dfs(nx, ny);
	}
}