백준 2573 빙산

백준 2573

총 두가지 작업을 해줘야 한다.
1. 현재 상태에서 빙하가 몇개로 나뉘어져있는지 확인
2. 매년 각각의 빙하의 높이 줄이기

첫 번째는 bfs를 돌려서 확인 하면 되고, 두 번째는 이중포문으로 하나씩 체킹해서 상하좌우에 0이 얼마나 있는지 확인해서 높이를 각각 줄이면 된다. 이 때, 높이를 줄일때 다른 빙하와 같이 줄여야 한다. 개별적으로 하나씩 줄이면 다른 빙하에 영향을 준다.

#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
int n, m;
int arr[301][301];
int vis[301][301]; 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int y; // 년도
int bfs() { // 몇개의 빙하로 나뉘어졌는지
	memset(vis, 0, sizeof(vis));
	int cnt = 0;
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!arr[i][j] || vis[i][j]) continue;
			vis[i][j] = 1;
			q.push({ i,j });
			while (!q.empty()) {
				pair<int, int> 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 || ny < 0 || nx >= n || ny >= m) continue;
					if (vis[nx][ny] || !arr[nx][ny]) continue;
					vis[nx][ny] = 1;
					q.push({ nx,ny });
				}
			}
			cnt++; // 빙하 덩어리 갯수
		}
	}
	return cnt;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

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

	while (bfs() < 2) {

		vector<int> v;
		int minus;
		for (int i = 0; i < n; i++) { 
			for (int j = 0; j < m; j++) {
				if (arr[i][j]) {
					minus = 0;
					for (int k = 0; k < 4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];

						if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

						if (!arr[nx][ny]) {
							minus++;
						}
					}
					v.push_back(minus); // 상하좌우 방향에서 줄어들어야할 높이
				}
			}
		}
		int ind = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j]) {
					arr[i][j] -= v[ind]; // 빙하 녹이기
					if (arr[i][j] < 0) arr[i][j] = 0;
					ind++;
				}
			}
		}
		
		y++;
		if (!bfs()) break;
	}
	if (bfs()<2) cout << 0 << '\n';
	else cout << y << '\n';
}