BOJ 2573 : 빙산

입력

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

출력

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

 

---

[BOJ 2584(G4) 리뷰]

쉬운듯 어려웠다.

빙산의 높이가 주어진다. 빙산은 주위에 인접한 바다의 개수에 영향을 받는다.

주위에 바다가 2개라면 1년뒤 빙산의 높이는 2만큼 줄어준다.

처음엔 빙산이 하나로 이어져 있지만 시간이 지나며 빙산이 녹음에따라 빙산이 2개로 나뉘는데 이렇게 빙산이 2개이상으로 나뉠때까지 총 몇년이 걸리는지 구해야 한다.

 

처음엔 BFS를 수행할때마다 현재 빙산의 높이에서 주위의 바다의 개수만큼 높이를 감소하도록 코딩했지만 이렇게 하면 1년단위로 빙산의 움직임을 구현할 수 없다는 문제가 있었다.

 

따라서 melt배열을 선언한 후에 현재 빙산의 위치가 1년뒤에 녹게될 값을 저장하고 1년이 지날때마다 현재높이를 감소시켰다. 반복문을 돌며 탐색을 수행하다가 영역이 2개이상으로 나뉘면 반복을 멈추고 출력한다. 만약 빙산을 다 탐색했는데도 녹는빙산이 하나도 없다는것은 이미 다 녹아있다는것이고 이것은 빙산이 한번에 다같이 녹는것이므로 0을 출력하면 된다.

 

---

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second
int board[302][302];
int check[302][302];
int melt[302][302];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1,  0, -1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}

	int year = 0;
	int area = 0;
	while (1)
	{
		for (int k = 0; k < n; k++)
		{
			fill(check[k], check[k] + m, 0);
		}
			
		area = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (check[i][j] != 0 || board[i][j]<=0) continue;
				area++;
				queue<pair<int, int>> Q;
				check[i][j] = 1;
				Q.push({ i,j });
				while (!Q.empty())
				{
					auto cur = Q.front();
					Q.pop();
					int cnt = 0;
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (board[nx][ny] <= 0) cnt++;
						if (check[nx][ny] != 0 || board[nx][ny] <= 0) continue;
						check[nx][ny] = 1;
						Q.push({ nx,ny });
					}
					melt[cur.X][cur.Y] = cnt;
				}
			}
		}

		if (area > 1) break;

		int count = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (melt[i][j] != 0)
				{
					board[i][j] -= melt[i][j];
					melt[i][j] = 0;
					count++;
				}
			}
		}

		if (count == 0) 
		{
			year = 0;
			break;
		}
		year++;
	}
	
	cout << year;

}