[1113] 수영장 만들기

https://www.acmicpc.net/problem/1113

1113번: 수영장 만들기

<문제>

뭔가 특이하고 복잡한 문제인거 같지만, H=벽의 높이일때 O(HNM)으로 풀리는 문제다.

풀이의 방향을 잘 잡으면 정말 쉽게풀 수 있지만, 그렇지 않으면 한참을 헤메기 좋은 문제인듯 싶다.

 

물을 한칸씩 채워넣는다고 생각할때,

bfs에서 가장자리(첫행or첫열or마지막행or마지막열)를 방문하면 그곳에는 물이 쌓일 수 없다.

만약 그러한 경우가 발생하지 않았다면, 기존에 방문한 정점을 다시한번 순회하며 물을 채워넣어준다.

채워넣은 만큼 정답을 업데이트 해주고, 해당 정점의 a[i][j]를 높이로 만들어주면

다음 높이를 탐색할때 중복으로 물의 양을 계산하는것을 방지할 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
typedef struct {
    int y, x;
} state;
int n, m, ans, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int a[55][55];
bool vst[55][55];
void f(int sy, int sx, int h) {
    memset(vst, 0, sizeof(vst));
    queue<state> q;
    q.push({sy, sx});
    vst[sy][sx] = true;
    vector<pi> v;
    v.clear();
    v.push_back({sy, sx});
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == 0 || cur.x == 0 || cur.y == n - 1 || cur.x == m - 1) {
            return;
        }
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (a[y][x] <= a[sy][sx] && vst[y][x] == false) {
                vst[y][x] = true;
                q.push({y, x});
                v.push_back({y, x});
            }
        }
    }
    for (auto i : v) {
        ans += (h - a[i.first][i.second]);
        a[i.first][i.second] = h;
    }
    return;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int i, j;
    char in[55][55];
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> in[i][j];
            a[i][j] = in[i][j] - '0';
        }
    for (int len = 2; len <= 9; len++) {
        memset(vst, 0, sizeof(vst));
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) continue;
                if (a[i][j] < len) {
                    f(i, j, len);
                }
            }
        }
    }
    cout << ans;
    return 0;
}