[백준 2573: 빙산] - C++

www.acmicpc.net/problem/2573

2573번: 빙산

 

 

#include<iostream>
#include<string>
#include<string.h>
using namespace std;

int n, m;
int map[300][300];
int check[300][300];
int checkTemp[300][300];
int result = 0;
int year = 0;
int dir[4][2] = {
	{-1,0}
	,{0,1}
	,{1,0}
	,{0,-1}
};

//얼음 몇 덩어리인지 세기용
void CheckIce(int _x, int _y)
{
	for (int i = 0; i < 4; i++)
	{
		int nextX = _x + dir[i][0];
		int nextY = _y + dir[i][1];

		if (nextX < 0 || nextY < 0 || n <= nextX || m <= nextY)
			continue;

		if (map[nextX][nextY] != 0 && !checkTemp[nextX][nextY])
		{
			checkTemp[nextX][nextY] = true;
			CheckIce(nextX, nextY);
		}
	}

}

//얼음 몇 덩어리인지 세기용
int Search(int _x, int _y)
{

	memset(checkTemp, false, sizeof(checkTemp));
	int cnt = 0;
	int result2 = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] != 0 && !checkTemp[i][j])
			{
				result2++;
				checkTemp[i][j] = true;
				CheckIce(i, j);
			}
		}
	}


	return result2;
}

//얼음 녹게함
void MeltIce(int _x, int _y)
{
	int cnt = 0;
	for (int i = 0; i < 4; i++)
	{
		int nextX = _x + dir[i][0];
		int nextY = _y + dir[i][1];

		if (nextX < 0 || nextY < 0 || n <= nextX || m <= nextY)
			continue;

		if (map[nextX][nextY] != 0 && !check[nextX][nextY])
		{
			check[nextX][nextY] = true;
			MeltIce(nextX, nextY);
		}

		if (map[nextX][nextY] == 0 && !check[nextX][nextY])
		{
			cnt++;
		}
	}

	map[_x][_y] -= cnt;

	if (map[_x][_y] <= 0)
	{
		map[_x][_y] = 0;
	}
}

int main() {

	cin >> n >> m;
	memset(map, 0, sizeof(map));

	//입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
		}
	}

	//계산
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] != 0 && !check[i][j])
			{
				check[i][j] = true;

				MeltIce(i, j); //얼음 녹이기
				year++;

				result = Search(i, j); //몇덩어리 인지 세기	
				

				if (1 < result) //2덩어리 이상이면 종료
				{
					cout << year << endl;
					return 0;
				}

				memset(check, false, sizeof(check));
				
			}
		}
	}


	cout << 0 << endl;
	return 0;
}