[C++] 백준 온라인 저지 2468번 안전 영역 풀이

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제

 

---

문제의 조건

 

 

1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 

 

 

2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 

 

3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데

같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 

 

 

즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 

 

2번의 경우에서 안전 영역의 갯수는 5개이다. 

 

 

4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 

이 때 안전 영역의 갯수는 4개이다. 

이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 

 

5. 어떤 영역의 높이 정보가 주어졌을 때 안전 영역의 최대 갯수를 구해서 출력하기 

 

---

풀이 과정

 

처음엔 비가 오는 양이 주어져 있지 않아서 뭔가 싶었는데 

비가 오는 양에 따라서 생기는 안전 영역의 갯수를 모두 조사해봐야 한다는 것을 알게 되어서 

비가 오지 않았을 때부터 최대 높이까지 비가 왔을 때까지 BFS로 안전 영역을 탐색하는 방식으로 코드를 짰습니다. 

 

1. 테스트 케이스 입력을 받으면서 가장 높은 높이를 저장해 놓는다. 

 

2. 비가 오는 최저 높이 0부터 최고 높이까지 반복하는 반복문을 만든다. 

 

3. BFS로 현재 강수량 높이보다 높은 지역을 탐색해서 그 갯수를 센다. 

 

4. 3번 과정이 끝나면 지금까지 셌던 갯수 중 최대값을 저장한다. 

 

 

* 이 문제의 반례

처음엔 현재 테스트 케이스의 최저 높이부터 시작할 수 있습니다. (제가 그랬었음 ㅋ..)

하지만

 

2

1 1

1 1

정답: 1

 

와 같은 케이스에서 최저 높이인 1부터 시작하면 제대로 탐색하지 못하기 때문에 정답으로는 0을 리턴하게 됩니다. 

그래서 최저 높이는 무조건 0부터 시작하는 것이 좋습니다. 

---

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main(int argc, const char * argv[])
{
    vector<vector<int>> dir; //BFS 탐색방향 
    dir.push_back({0,1});
    dir.push_back({0,-1});
    dir.push_back({1,0});
    dir.push_back({-1,0});
    
    int N;
    cin >> N;
    
    int maxHeight = 1;
    vector<vector<int>> areas(N, vector<int>(N, 0));
    for (int i = 0; N > i; i++)
    {
        for (int j = 0; N > j; j++)
        {
            int h;
            cin >> h;
            areas[i][j] = h;
            maxHeight = max(maxHeight, h); //입력 받으면서 최대 높이도 저장 
        }
    }
    
    int answer = 0;
    //최저 높이부터 시작해서 최고 높이보다 작거나 같을 때까지 반복
    for (int minHeight = 0; maxHeight >= minHeight; minHeight++)
    {
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        int areaCount = 0;
        for (int i = 0; areas.size() > i; i++)
        {
            for (int j = 0; areas[i].size() > j; j++)
            {
                //현재 강수량보다 커야 물에 잠기지 않은 지역임 
                if (areas[i][j] > minHeight && !visited[i][j])
                {
                    queue<pair<int, int>> q;
                    q.emplace(make_pair(i, j));
                    visited[i][j] = true;
                    
                    while (!q.empty())
                    {
                        auto curArea = q.front();
                        q.pop();
                        
                        for (int k = 0; dir.size() > k; k++)
                        {
                            auto nextArea = make_pair(curArea.first + dir[k][0], 
                            curArea.second + dir[k][1]);
                            if (nextArea.first < 0 || nextArea.first >= N
                                || nextArea.second < 0 || nextArea.second >= N)
                                continue;
                            if (!visited[nextArea.first][nextArea.second]
                                && minHeight < areas[nextArea.first][nextArea.second])
                            {
                                q.emplace(nextArea);
                                visited[nextArea.first][nextArea.second] = true;
                            }
                        }
                    }
                    areaCount++;
                }
            }
        }
        //현재 강수량에 대해 BFS가 끝나면 최대값으로 정답 갱신 
        answer = max(answer, areaCount);
    }
    
    cout << answer;
    
    return 0;
}