전형적인 BFS 문제이다.
새로운 아이디어를 요구하지는 않지만, BFS로 구현할 수 있는 문제들을 짬뽕해놓은 느낌의 문제로 구현해야 할 것이 많으며 실수할 여지가 있다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[302][302];
int vis[302][302];
int melt[302][302];
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] ={0, 1, 0, -1};
int main(void) {
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 >> board[i][j];
}
}
// 분리된 빙산 수
int ans = 0;
int year = 0;
while(true) {
// 초기화
for(int i = 0; i < n; i++) {
fill(vis[i], vis[i]+m, 0);
fill(melt[i], melt[i]+m, 0);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(board[i][j] == 0 || vis[i][j] != 0) continue;
queue<pair<int, int>> Q;
Q.push({i, j});
vis[i][j] = 1;
ans++;
while(!Q.empty()) {
auto cur = Q.front(); Q.pop();
int z_number = 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) z_number++;
if(vis[nx][ny] != 0 || board[nx][ny] == 0) continue;
Q.push({nx, ny});
vis[nx][ny] = 1;
}
melt[cur.X][cur.Y] = z_number;
}
}
}
// BFS가 끝난 뒤에 녹여준다.
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(melt[i][j]) {
while(melt[i][j]--) {
if(board[i][j] <= 0) break;
board[i][j]--;
}
}
}
}
if(ans > 1) {
cout << year;
return 0;
}
else if(ans == 0) {
cout << 0;
return 0;
}
else {
ans = 0;
}
year++;
}
}