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

문제 링크

2573번: 빙산

문제 요약

빙산의 높이가 주어진다. 빙산은 매 시간마다 바다가 인접한 면의 수만큼 녹아내리는데, 빙산이 두 조각 이상으로 나눠질 때까지 걸리는 시간을 구해야 한다.

접근 방법

단순 구현 문제입니다. 주의해야할 점은 빙산의 각 부분은 동시에 녹아내리기 때문에, 녹아내릴 양을 미리 기록해 두었다가 한꺼번에 처리해야 한다는 것입니다. 대부분 이 부분은 쉽게 캐치할 수 있습니다.

빙산이 두 조각 이상인지 판단하는 방법은, 최초로 빙산 조각을 만나 그래프 탐색을 한 번 돌린 상태에서, 방문하지 않은 빙산 조각을 만나게 되면 두 조각 이상이라고 판단을 할 수 있습니다.

워낙 쉬운 문제라 한 번에 AC를 받을 수 있을거라고 생각했는데 반복문에서 M 대신 N을 쓰거나, 디버깅용 코드를 지우지 않고 제출하는 황당한 실수를 여러번 해서 WA를 몇번 받았습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 301

using namespace std;

int n, m, b[MAX][MAX], cnt[MAX][MAX], dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool visited[MAX][MAX];

void bfs(int r, int c)
{
	queue<pair<int, int>> q;
	q.push({ r, c });
	visited[r][c] = true;

	while (!q.empty())
	{
		auto now = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nr = now.first + dir[i][0], nc = now.second + dir[i][1];
			if (nr >= 1 && nc >= 1 && nr <= n && nc <= m && !visited[nr][nc] && b[nr][nc])
				q.push({ nr, nc }), visited[nr][nc] = true;
		}
	}
}

bool check(void)
{
	memset(visited, false, sizeof(visited));
	bool flag = false;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (b[i][j] && !visited[i][j])
			{
				if (!flag)
					bfs(i, j), flag = true;
				else
					return true;
			}
		}
	}
	return false;
}

int main(void)
{
	FASTIO; 
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> b[i][j];

	int res = 0;
	while(1)
	{
		if (check())
		{
			cout << res << endl;
			return 0;
		}

		bool flag = true;
		memset(cnt, 0, sizeof(cnt));
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= m; k++)
			{
				if (b[j][k])
				{
					flag = false;
					for (int l = 0; l < 4; l++)
					{
						int r = j + dir[l][0], c = k + dir[l][1];
						if (r >= 1 && c >= 1 && r <= n && c <= m && !b[r][c])
							cnt[j][k]++;
					}
				}
			}
		}

		if (flag)
			break;

		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= m; k++)
				b[j][k] = (b[j][k] - cnt[j][k] >= 0 ? b[j][k] - cnt[j][k] : 0);
		res++;
	}

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