수영장 만들기

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1057 ~ 1248 
// 높이가 9~1까지 물로 채운뒤 BFS로 해당 높이보다 작은 수를 해당 수로 채운 뒤 연결된 점들중 하나라도 영역을 벗어나면 fail
int N,M,ans;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int board[55][55];
int t_board[55][55];
bool end_board[55][55];
bool vis[55][55];
int water = 9;
// 해당 좌표에 대해 4방향 검사해서 하나라도 영역에 벗어나면 out!
bool check4DIR(int y, int x)
{   
    for(int dir=0;dir<4;dir++)
    {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if(nx<0 or ny<0 or nx>=M or ny>=N) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
    {
        string s;
        cin >> s;
        int j=0;
        for(auto a : s) board[i][j++] = a-'0';
    }

    while(water >= 1)
    {
        /* t_board 준비 */
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                t_board[i][j] = board[i][j];
        /* vis 준비 */
        for(int i=0;i<N;i++)
            fill(vis[i], vis[i]+M, false);
        /* water보다 작은 곳을 water로 채우기 */
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(t_board[i][j] < water) t_board[i][j] = water;
        /* 모든 좌표에 대해 연결된 덩어리가 둘러쌓인 길이를 구함 */
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(vis[i][j] or t_board[i][j] > water or end_board[i][j]) continue;
                queue<pair<int,int>> q;
                vector<pair<int,int>> v;
                int tot_water = t_board[i][j] - board[i][j];
                bool flag = true;
                vis[i][j] = true;
                int cnt=1;
                q.push({i,j});
                v.push_back({i,j});
                while(!q.empty())
                {
                    auto cur = q.front(); q.pop();
                    for(int dir=0;dir<4;dir++)
                    {
                        int ny = cur.first + dy[dir];
                        int nx = cur.second + dx[dir];
                        if(nx<0 or ny<0 or ny>=N or nx>=M){
                            flag = false;
                            continue;
                        }
                        if(vis[ny][nx] or t_board[ny][nx] > water) continue;
                        // 해당 좌표를 기준으로 4방향중 하나라도 영역을 벗어나면 물이 계속 새기때문에 실패
                        if(!check4DIR(ny, nx)) flag = false;
                        q.push({ny, nx});
                        v.push_back({ny,nx});
                        vis[ny][nx] = true;
                        tot_water += t_board[ny][nx] - board[ny][nx];
                        cnt++;
                    }
                }
                if(flag == true){
                    /* 수영장에 포함되는 영역들의 end처리
                       --> water을 9부터1로 줄여가기 때문에 더이상 큰 영역으로 나올 수 없다 */
                    for(int a=0;a<v.size();a++)
                        end_board[v[a].first][v[a].second] = true;
                    /* 높이의 차이가 있어야 흐르지 않는다고 가정하고 tot_water을 구한 뒤
                       총 면적의 개수만큼 더하면 높이가 같을 때 흐르지 않는 것으로 계산 가능 */
                    ans += tot_water;
                    ans += cnt;
                }
            }
        }
        water--;
    }
    cout << ans;
    return 0;
}

• 로직
  • 물의 양을 9 --> 1로 줄여가며 각 영역마다 담을 수 있는 최대 물을 저장
  • 문제와 다르게 물과 땅의 높이차가 있어야 흐르지 않는 것으로 이해하고 문제를 풀었다
    (영역의 개수를 cnt로 구한 뒤 마지막에 더해주면 동일한 높이에서 흐르지 않는것과 같은 계산이 가능!)
  • 해당 영역이 수영장이 될 수 있는 조건인 둘러쌓인 상태를 검사하기 위해서 범위 검사를 사용
    --> 연결된 영역중 하나의 좌표라도 4방향이 board[][]를 넘어가면 둘러쌓이지 않은 것임
  • 수영장의 조건을 만족하는 영역은 tot_water과 cnt를 더해서 물의 양을 구한다
    (vector를 이용해서 해당 영역에 대한 end처리를 해서 더 낮은 물에서 수영장이 구성되어도 답으로 처리되지 않게 함)

• 느낀 점
  • 처음에 땅과 물의 높이차가 있어야 흐르지 않는것으로 이해하고 문제를 풀었으나,
    다행히 영역의 개수를 이용해서 문제의 의도와 같은 계산을 할 수 있었다
  • 어렵다