✔ 문제해결전략
- 그래프 탐색
- BFS(Breadth First Search)
✔ 해결과정
- 처음에 한 번의 BFS 사이클 내에 모든 것을 해결하려고 했는데 잘되지 않아서 헤맸다. 생각해 보면 처음에 빙산이 녹는 것에 대해 map을 업데이트하기 위해 한 사이클을 돌리고, 업데이트된 map에 대해 빙산 개수를 구하기 위해 두 번째 사이클을 돌려도 BFS 한 사이클 돌린 거랑 시간 복잡도가 같다.
- 그리고 map을 업데이트하는 과정에서 먼저 방문한 점이 업데이트되어 버리면 그 결과가 인접한 점의 업데이트에 영향을 미치므로 입력받은 원본 그대로의 map에서 각 점에 대한 update 값(isolatedFLag)을 구하고 모든 점을 동시에 업데이트해야 한다.
- 정리하면 각 점에 대한 isolatedFlag를 구하기 위한 BFS 한 사이클, map 업데이트, 빙산을 구하기 위한 BFS 한 사이클을 돌리면 된다.
- 추가적으로 빙산이 분리되는 최초의 시간을 구하기 위해 위 과정을 반복해야 하는데 매 과정이 시작될 때마다 map, vis, isolatedFlag를 초기화해주어야 한다.
- 마지막으로 빙산이 나누어지지 않는 edge case도 생각해야 하는데(이거 고려 안 했다가 엄청 틀렸다..) 마지막 if문이 그 조건이다. 마지막 if문 2개의 순서도 주의해야 한다.
#include <bits/stdc++.h>
using namespace std;
int mapp[300][300];
int isolatedFlag[300][300];
int vis[300][300];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mapp[i][j];
}
}
int num, year = 0;
while (1) { // year pass by...
memset(vis, 0, sizeof(vis));
memset(isolatedFlag, 0, sizeof(isolatedFlag));
num = 0;
// update isolatedFlag
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mapp[i][j] == 0 or vis[i][j]) continue;
queue < pair < int, int > > Q;
vis[i][j] = 1;
Q.push({
i,
j
});
while (!Q.empty()) {
auto cur = Q.front();
Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] == 0 && mapp[nx][ny] != 0) {
vis[nx][ny] = 1;
Q.push({
nx,
ny
});
} else if (mapp[nx][ny] == 0) { // sea
if (mapp[cur.first][cur.second] > 0) isolatedFlag[cur.first][cur.second]++;
}
}
} // while
} // j
} // i
// update map
for (int k = 0; k < n; k++) {
for (int p = 0; p < m; p++) {
mapp[k][p] -= isolatedFlag[k][p];
if (mapp[k][p] < 0) mapp[k][p] = 0;
}
}
memset(vis, 0, sizeof(vis));
// count island
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mapp[i][j] == 0 or vis[i][j]) continue;
num++;
queue < pair < int, int > > QQ;
vis[i][j] = 1;
QQ.push({
i,
j
});
while (!QQ.empty()) {
auto cur = QQ.front();
QQ.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] == 0 && mapp[nx][ny] != 0) { // unvisited island
vis[nx][ny] = 1;
QQ.push({
nx,
ny
});
}
}
} // while
} // j
} // i
year++;
if (num == 0) {
cout << 0;
return 0;
}
if (num != 1) break;
} // while
cout << year;
}
✔ Check Point
- map 업데이트 과정에서 먼저 방문한 점이 업데이트되면 다른 점의 업데이트에 영향을 미치는 경우, 업데이트Flag 구하는 과정과 업데이트하는 과정을 분리해야 한다
- 특정한 값(MIN, MAX)을 구하기 위해 BFS 등을 반복할 때 매 과정 시작에 vis 등을 초기화해주어야 한다는 것 주의
- edge case(빙산이 나누어지지 않는 경우 등)에 주의할 것
BFS를 응용하면 이렇게 낼 수도 있구나라는 생각이 들었다. 풀면서 얻어 가는 것이 많았다.
귀찮아서 문제만 풀고 포스팅을 미루고 있었는데 오늘부터 다시 하나씩 정리 시작... 리팩토링은 다음에 하는 걸로