백준 1113 - 수영장 만들기

문제 설명

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661
61116
16661

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

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

 

---

 

 

 

 

 

 

제한 사항

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

---

 

 

 

 

 

 

풀이

문제를 요약하면, 각 칸의 높이가 다른 수영장의 물을 채우는 문제이다.

해당 칸의 상하좌우가 해당 칸보다 크다면 물을 담을 수 있다.

 

문제를 풀기 위해서는 1단계씩 물을 채워나간다고 생각하면 된다.

즉, 가장 낮은 높이인 1만큼의 물을 채울 수 있는 칸을 카운팅하는 것이다.

그렇다면 해당 높이의 물을 채울 수 있는 칸을 구하는 방법이 필요하다.

 

수영장 테두리에 해당 단계의 높이만큼의 가상의 벽을 만들어 BFS를 진행하면 쉽게 구할 수 있다.

우선, 초기 상황은 다음과 같이 설정할 수 있다.

이상태에서 {0, 0}에서부터 BFS를 시작한다.

BFS는 목표 높이보다 낮은 칸을 포함하며 진행된다.

BFS가 완료되면 다음과 같은 상황이 된다.

즉, BFS를 진행하면 목표 높이보다 높은 칸에 가로막혀 안쪽에 접근할 수 없게 된다.

void BFS(vector<vector<int>>& Pool, int l)
{
    Pool[0][0] = l;
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(Pool.size(), vector<bool>(Pool[0].size(), false));
    visited[0][0] = true;

    q.push({ 0,0 });

    while (!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];

            if (newY < 0 || newY >= N + 2 || newX < 0 || newX >= M + 2) continue;
            if (visited[newY][newX]) continue;

            visited[newY][newX] = true;
            if (Pool[newY][newX] >= l) continue;

            Pool[newY][newX] = l;
            q.push({ newY, newX });
        }
    }
}

 

그렇다면 이제 벽으로 둘러싸인 안쪽 영역 중, 목표 높이보다 작은 칸이 있다면 물을 채우면 된다.

for (int y = 1; y <= N; y++)
{
    for (int x = 1; x <= M; x++)
    {
        if (Pool[y][x] < i)
        {
            Pool[y][x]++;
            answer++;
        }
    }
}

현재 상황에는 1보다 작은 칸이 없기 때문에 물을 채울 수 없다.

다음 단계부터 물을 채울 수 있다는 뜻이다.

 

물의 높이가 1~9이기 때문에 연산 수가 그렇게 많지는 않지만 최적화를 시킨다면, 최저 높이와 최고 높이를 입력에서 계산하여 불필요한 연산을 줄일 수 있다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { -1, 0 , 1, 0 };
vector<int> dx = { 0, 1 , 0, -1 };

void BFS(vector<vector<int>>& Pool, int l)
{
    Pool[0][0] = l;
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(Pool.size(), vector<bool>(Pool[0].size(), false));
    visited[0][0] = true;

    q.push({ 0,0 });

    while (!q.empty())
    {
        auto [y, x] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int newY = y + dy[i];
            int newX = x + dx[i];

            if (newY < 0 || newY >= N + 2 || newX < 0 || newX >= M + 2) continue;
            if (visited[newY][newX]) continue;

            visited[newY][newX] = true;
            if (Pool[newY][newX] >= l) continue;

            Pool[newY][newX] = l;
            q.push({ newY, newX });
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    vector<vector<int>> Pool(N + 2, vector<int>(M + 2, 0));
    int maxNum = 0;
    int minNum = 10;
    int answer = 0;

    for (int i = 1; i <= N; i++)
    {
        string temp;
        cin >> temp;
        for (int j = 1; j <= M; j++)
        {
            int t = temp[j - 1] - '0';
            Pool[i][j] = t;
            maxNum = max(maxNum, t);
            minNum = min(minNum, t);
        }
    }


    for (int i = minNum; i <= maxNum; i++)
    {
        BFS(Pool, i);

        for (int y = 1; y <= N; y++)
        {
            for (int x = 1; x <= M; x++)
            {
                if (Pool[y][x] < i)
                {
                    Pool[y][x]++;
                    answer++;
                }
            }
        }
    }
       
    cout << answer;

	return 0;
}

---