백준] 2573 - 빙산(한국정보올림피아드;KOI 2006 초등부)

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {
{1,0},
{0,1},
{-1,0},
{0,-1}
};
int w, h;
vector<vector<int> > curMap;
vector<vector<int> > nextMap;
vector<vector<bool> > visit;
void dfs(int y, int x)
{
	visit[y][x] = true;

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i][0], nx = x + dir[i][1];

		if (((ny >= 0 && ny < h) && (nx >= 0 && nx < w))
			&& (visit[ny][nx] == false && curMap[ny][nx] > 0))
			dfs(ny, nx);
	}
}
void melt(int y, int x)
{
	int water = 0;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i][0], nx = x + dir[i][1];
		if ((ny >= 0 && ny < h) && (nx >= 0 && nx < w) && curMap[ny][nx]==0)
			water++;
	}
	nextMap[y][x] = ((curMap[y][x] - water) > 0) ? (curMap[y][x] - water) : 0;
}
bool isGone()
{
	for (int y = 0; y < h; y++)
		for (int x = 0; x < w; x++)
			if (curMap[y][x] > 0)
				return false;
	return true;
}
int main(void)
{
	cin >> h >> w;
	curMap = vector<vector<int> >(h, vector<int>(w));
	nextMap = vector<vector<int> >(h, vector<int>(w));
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> curMap[i][j];
	int year = 0;
	while (1)
	{
		if (isGone())
		{
			cout << 0;
			return 0;
		}
		visit = vector<vector<bool> >(h, vector<bool>(w, false));
		int island = 0;
		for (int y = 0; y < h; y++)
		{
			for (int x = 0; x < w; x++)
			{
				if (curMap[y][x] && visit[y][x] == false)
				{
					dfs(y, x);
					island++;
					if (island > 1)
					{
						cout << year;
						return 0;
					}
				}
			}
		}

		for (int y = 0; y < h; y++)
			for (int x = 0; x < w; x++)
				if (curMap[y][x])
					melt(y, x);
		curMap = nextMap;
		year++;
	}
	return 0;
}

Tip

빙산을 녹이는 과정과 빙산이 쪼개지는 부분을 체크하는 과정, 그리고 빙산이 일시에 다 녹았는지 판단하는 과정이 필요하다. 빙산이 쪼개진 것을 확인하는 것은 DFS나 BFS, 둘 중 하나 사용해서 판별하면 된다.