bfs를 이용한 문제이다. 과정은 아래와 같다.
- 빙산이 모두 녹았는지 확인한다.
- 빙산이 두덩이 이상으로 분리되었는지 확인한다.
- 빙산을 녹인다.
반복문을 이용해 위의 과정을 반복해주었다. 빙산이 모두 녹았는지는 백터를 이용해 확인해주었다. 처음 입력값을 받을 때 0이 아닌 곳의 위치를 백터에 저장해주고 백터의 크기가 0이 된 경우를 빙산이 모두 녹았다고 판단하였다. 두덩이 이상으로 분리된지 확인하는 것은 bfs를 이용하였다. 벡터를 차레로 접근하면서 해당 위치와 인접한 빙산을 모두 구하고 이를 카운트하며 카운트가 2 이상이 된 경우를 두덩이 이상으로 분리되었다고 판단했다. 빙산을 녹이는 부분이 중요한데, 녹이는 과정에서 0이된 빙산을 기존에 있던 0과 분리하여 판단하기 위해 check
를 하여 녹이는 과정에서의 오류를 잡아주었다. 이를 반복하여 두덩이 이상이 될 경우 걸린 시간을 출력해주고, 다 녹은 경우 0을 출력해주었다.
생각보다 오래 걸린 문제였다. 앞서 말한 빙산을 녹이는 알고리즘 부분에서 녹이는 과정에 0이된 경우를 기존 0과 같다고 판단해 잘못된 결과를 내어 실패가 계속해서 났었고, 이를 찾는 과정이 오래걸렸다. check
를 꼭 사용하도록 하자.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M, res = 0;
int A[300][300];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<pair<int, int>> q;
vector<pair<int, int>> v;
bool check[300][300];
void bfs() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
check[i][j] = false;
}
}
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
int count = 0;
check[y][x] = true;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (check[ny][nx]) continue;
if (A[ny][nx] == 0) count++;
}
A[y][x] -= count;
if (A[y][x] < 0) {
A[y][x] = 0;
}
}
for (int i = 0; i < v.size(); i++) {
int y = v[i].first;
int x = v[i].second;
if (A[y][x] == 0) {
v.erase(v.begin() + i);
i--;
}
}
}
void check_bfs(int a, int b) {
queue<pair<int, int>> tmp;
tmp.push({ a,b });
check[a][b] = true;
while (!tmp.empty()) {
int y = tmp.front().first;
int x = tmp.front().second;
int count = 0;
tmp.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (A[ny][nx] == 0) continue;
if (check[ny][nx]) continue;
tmp.push({ ny,nx });
check[ny][nx] = true;
}
}
}
void solution() {
while(1){
if (v.size() == 0) break;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
check[i][j] = false;
}
}
int count = 0;
for (int i = 0; i < v.size(); i++) {
int y = v[i].first;
int x = v[i].second;
if (check[y][x]) continue;
check_bfs(y, x);
count++;
}
if (count >= 2) break;
for (int i = 0; i < v.size(); i++) {
q.push({ v[i].first, v[i].second });
}
bfs();
res++;
}
if (v.size() == 0) {
cout << 0 << "\n";
}
else {
cout << res << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
if (A[i][j] != 0) {
v.push_back({ i,j });
}
}
}
solution();
return 0;
}