BOJ 2573 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다.

구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것

2개만 신경써주면 된다.

 

			if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
			else if (!vis[nx][ny]) {
				q.push({ nx,ny });
				vis[nx][ny] = true;
			}

 

상하좌우를 돌면서 방문하지 않았고 0이라면 현재 값을 1 줄여주고

방문하지 않은 빙하라면 큐에 넣어준다.

그리고 갱신해준 후 0 이하라면 0으로 수정해주면 된다.

 

#include <iostream>
#include <queue>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
int n, m, ans, ar[301][301];
bool vis[301][301];

void bfs(int x, int y) {
	vis[x][y] = true;
	q.push({ x,y });

	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
			else if (!vis[nx][ny]) {
				q.push({ nx,ny });
				vis[nx][ny] = true;
			}
		}
		if (ar[cur.first][cur.second] < 0) 
			ar[cur.first][cur.second] = 0;
	}
}

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

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

	while (1) {
		for (int i = 0; i < n; ++i) fill(vis[i], vis[i] + m, false);

		int land = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (vis[i][j] || !ar[i][j]) continue;
				bfs(i, j);
				land++;
			}
		}

		if (land > 1) break;
		else if (land == 0) {
			ans = 0; break;
		}
		ans++;
	}

	cout << ans << endl;

	return 0;
}