[백준] 1113번 수영장 만들기

물이 차는 부분을 구하기 위해 Simulation 해보는 문제이다. Simulation을 통해 풀어보자.

문제

---

힌트

이문제의 경우에는 힌트를 주기가 어렵다. 사실상 방식의 문제에서 틀리는 경우가 많을 것이라고 생각한다. 굳이 찾아서 준다면… bfs를 잘 활용하면 풀이가 쉬워질 수 있다.

코드 자세히 보기

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
vector<vector<int>> memo(55, vector<int> (55, 0));
class point{
    public:
    int y;
    int x;
};
int bfs(int point_y, int point_x, int height,  vector<vector<int>> land)    //실제로 채워지는 블럭의 수를 찾는 bfs함수
{
    queue<point> block;
    vector<point> cardinal_point = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    int count = 1;
        bool check = false;
    block.push({point_y, point_x});
    while(!block.empty())
    {
        int st_y = block.front().y;
        int st_x = block.front().x;
        block.pop();
        for(int i = 0; i < 4; i++)
        {
            int next_y = st_y + cardinal_point[i].y;
            int next_x = st_x + cardinal_point[i].x;
            if(next_y < 0 || next_x < 0 || next_y > n - 1 || next_x > m - 1)    //가장자리까지 이어지게 되면 수영장의 물이 빠진다... 이경우를 제외시키자
            {
                check = true;
                continue;
            }
            if(memo[next_y][next_x] == 1)
                continue;
            if(land[next_y][next_x] < height)
            {
                block.push({next_y, next_x});
                memo[next_y][next_x] = 1;
                count++;
            }
        }
    }
    if(check)
        return 0;
    return count;
}
int find(int height, vector<vector<int>> land)  //각 층마다 채워질수 있는 블럭을 찾는 함수
{
    int ans = 0;
    vector<vector<int>> reset(55, vector<int>(55, 0));
    memo = reset;   //방문했던 곳을 다시 리셋 시켜야 한다.
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(memo[i][j] == 1)
                continue;
            if(land[i][j] < height)
            {
                memo[i][j] = 1;
                ans += bfs(i, j, height, land);
            }
        }
    }
    return ans;
}
int main(void)
{
    cin >> n >> m;
    int height = 0;
    int answer = 0;
    vector<vector<int>> land(55, vector<int> (55, 0));
    for(int i = 0; i < n; i++)
    {
        string st;
        cin >> st;
        for(int j = 0; j < st.size(); j++)
        {
            land[i][j] = (int)st[j] - '0';
            height = max(height, land[i][j]);
        }
    }
    for(int i = 1; i <= height; i++)
        answer += find(i, land);
    cout << answer << "\n";
}

---

문제 풀이

이번 문제의 경우 dfs의 활용을 극대화 시켜야 한다. 또한 한꺼번에 구하려고 하는 첫시도는 쉽지 않다는 것을 알아차렸어야 한다. 만약 한꺼번에 푸는게 쉽지 않다면 단계를 나누어서 생각하는 방식을 활용하는 것도 좋다. 이 문제의 경우 한꺼번에 구하기 위해서는 가장 낮은 수영장 가장자리 값을 알아야 하는데 이를 구하는 방식을 생각해내지 못했다. 다음에는 첫시도를 통해 풀 수 있을지를 생각해보는 것도 좋을 것 같다. 그러한 풀이 방식이 있을까..??

문제 결과

문제 출처 https://www.acmicpc.net/problem/1113