Tip - 물 채우기와 관련된 BFS

물 채우기와 관련된 BFS

2차원에서 칸들이 있고, 물을 채웠을 때 얼마나 물이 고이는지 구하는 문제들이 있다.

대략 다음과 같은 문제들이다.

• BOJ 14324 - Rain (Small)
• BOJ 14325 - Rain (Large)
• BOJ 15730 - 수영장 사장님
• BOJ 1113 - 수영장 만들기
• BOJ 2276 - 물 채우기
• BOJ 12467 - Rains Over Atlantis (Small)

풀이

이런 물채우기식 BFS는 정형화된 풀이법을 알고 있으면 쉽다.

우선 어디서부터 채워나가기보다는, 일단 모든 칸이 $\infty$만큼 높이를 채울 수 있다고 가정하고 시작하는 것이다.

바깥과 연결되어있는 칸들은 일단 $h[y][x]$ 만큼만 높이를 채울 수 있다고 고정해둔다.

모든 과정이 끝난 후, 정답$=\displaystyle \sum_{y=0}^{Y-1}\sum_{x=0}^{X-1} \left( can[y][x]-h[y][x] \right)$ 이다.

$can[y][x]$ 는 $(y,x)$에 최대 얼만큼 물 높이가 될 수 있는지를 가지고 있는 배열이다.

이제, 처음에 큐에 넣어둔 바깥쪽 칸들부터 BFS를 돌리면서 어떤 부분의 높이가 현재만큼 차있을 수 없는 경우라면 $can[y][x]$ 를 줄여주면서 큐에 넣는다.

어떤 지점의 높이가 $h$ 만큼 차있는데, 바로 인접한 지점의 높이가 $h$ 보다 높게 차있을 수 없다는 점을 이용한다.

시간 복잡도

기본적으로 모든 칸을 보는데 $O(N^2)$ 라고 봤을 때, 높이가 변하며 계속해서 동일한 위치도 큐에 들어가기 때문에 모든 높이가 다르다면 최악의 경우 $O(N^4)$ 라고 생각이 되지만, 그것보다 훨씬 빠르게 돈다.

왜냐면 특정 물의 높이를 변화시킬 수 있는건 인접한 4칸 뿐이기 때문에 실제로는 $O(N^2)$ 과 크게 다르지 않다고 봐도 무방하다.

코드

BOJ 14325 - Rain (Large)

를 푸는 코드이다.

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;  
}