Tip - 물 채우기와 관련된 BFS
물 채우기와 관련된 BFSPermalink
2차원에서 칸들이 있고, 물을 채웠을 때 얼마나 물이 고이는지 구하는 문제들이 있다.
대략 다음과 같은 문제들이다.
- BOJ 14324 - Rain (Small)
- BOJ 14325 - Rain (Large)
- BOJ 15730 - 수영장 사장님
- BOJ 1113 - 수영장 만들기
- BOJ 2276 - 물 채우기
- BOJ 12467 - Rains Over Atlantis (Small)
풀이Permalink
이런 물채우기식 BFS는 정형화된 풀이법을 알고 있으면 쉽다.
우선 어디서부터 채워나가기보다는, 일단 모든 칸이 만큼 높이를 채울 수 있다고 가정하고 시작하는 것이다.
바깥과 연결되어있는 칸들은 일단 만큼만 높이를 채울 수 있다고 고정해둔다.
모든 과정이 끝난 후, 정답 이다.
는 에 최대 얼만큼 물 높이가 될 수 있는지를 가지고 있는 배열이다.
이제, 처음에 큐에 넣어둔 바깥쪽 칸들부터 BFS를 돌리면서 어떤 부분의 높이가 현재만큼 차있을 수 없는 경우라면 를 줄여주면서 큐에 넣는다.
어떤 지점의 높이가 만큼 차있는데, 바로 인접한 지점의 높이가 보다 높게 차있을 수 없다는 점을 이용한다.
시간 복잡도Permalink
기본적으로 모든 칸을 보는데 라고 봤을 때, 높이가 변하며 계속해서 동일한 위치도 큐에 들어가기 때문에 모든 높이가 다르다면 최악의 경우 라고 생각이 되지만, 그것보다 훨씬 빠르게 돈다.
왜냐면 특정 물의 높이를 변화시킬 수 있는건 인접한 4칸 뿐이기 때문에 실제로는 과 크게 다르지 않다고 봐도 무방하다.
코드Permalink
를 푸는 코드이다.
const int inf = 1e9;
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
void solve() {
int Y, X;
cin >> Y >> X;
vvi b(Y, vi(X));
auto can = b;
fv2(b);
queue<pi> q;
for (int y = 0; y < Y; y++)
for (int x = 0; x < X; x++) {
if (y == 0 || y == Y - 1 || x == 0 || x == X - 1) {
can[y][x] = b[y][x];
q.push({y, x});
} else {
can[y][x] = inf;
}
}
while (sz(q)) {
auto[y, x] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d], nx = x + dx[d];
if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {
int h = can[y][x];
if (can[ny][nx] > h) {
can[ny][nx] = max(h, b[ny][nx]);
q.push({ny, nx});
}
}
}
}
int ans = 0;
for (int y = 0; y < Y; y++) for (int x = 0; x < X; x++) ans += can[y][x] - b[y][x];
cout << ans << endl;
}
Comments