[ 백준 2468 ] 안전 영역 (C++)

백준의 안전영역(2468) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 어떤 지역의 한 변의 길이와, 그 지역의 높이 정보가 주어진다.

- 장마철에 내리는 비의 양에 의해서 지역은 침수가 된다.

- 내리는 비의 양보다 높이가 낮거나 같은 지역은 침수가 된다.

- 침수되지 않은 땅을 안전영역이라고 하며, 여기서 영역이라고 하는 것은, 상하좌우 중 한 방향으로라도 침수되지 않은

  땅끼리 연결되 있는 땅덩어리를 의미한다.

- 비가 내릴 때, 안전영역의 최대 갯수를 구하는 것이 문제이다.

[ 문제풀이 ] 

1) 문제에서 보면, 내리는 비의 양이 정해지지 않았다. 즉, 비의 양은 0부터 무한대 까지 내릴 수 있음을 의미한다.

2) 그렇다고 무한번 반복문을 돌릴 수는 없기 때문에, 처음 높이 정보를 입력받을 때, 본인은 최대 높이 값을 저장했다.

3) 반복문을 통해 비의 양을 0부터 무한대까지 반복문을 돌리는데, 그 반복문 안에서는 비의 양에 따라 침수되는 땅을

   0으로 표시했다.

   - 높이정보는 1부터 100이하의 숫자이므로 0으로 표시가능.

   - 입력받은 MAP에서 수정을 해버리면, 기존의 MAP에 대한 정보가 사라지기 때문에, MAP을 복사하는 과정이 있다.

4) 0으로 표시된 복사된 맵으로 BFS를 실행한다. 안전영역의 갯수는 BFS함수가 실행된 횟수와 같으므로, BFS가

   불릴 때 마다 Count를 해주는 변수만 있으면 쉽게 구할 수 있다.

5) 비의 양에 따라 안전영역의 갯수를 현재 최대 갯수의 안전영역과 비교해주면서, 값을 갱신해 간다.

6) 비의 양이 처음에 저장해둔 최대 높이 값보다 커지면 반복문을 종료한다. 

   - 비의 양이 최대 높이 값 보다 크다는 말은, 그 정도의 비가 내리게 되면 모든 지역이 침수된다는 의미이고, 안전영역이

     0이 된다는 것이다. 그 상태에서 비의 양이 더 늘어나는 것은 해보지 않아도 무조건 안전영역의 갯수가 0일 것이고

     더 이상 실행을 하지 않아도 됨을 의미한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, Max_Height_Area, Answer, Num_Area;
int MAP[MAX][MAX], C_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    Max_Height_Area = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] > Max_Height_Area) Max_Height_Area = MAP[i][j];
        }
    }
}
 
void Copy_MAP()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
void Make_MAP(int H)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C_MAP[i][j] <= H) C_MAP[i][j] = 0;
            else V.push_back(make_pair(i, j));
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N)
            {
                if (Visit[nx][ny] == false && C_MAP[nx][ny] != 0)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Solution()
{
    for (int H = 0; ; H++)
    {
        Num_Area = 0;
        V.clear();
        memset(Visit, false, sizeof(Visit));
        if (H > Max_Height_Area) break;
        Copy_MAP();
        Make_MAP(H);
 
        for (int i = 0; i < V.size(); i++)
        {
            int x = V[i].first;
            int y = V[i].second;
 
            if (Visit[x][y] == false)
            {
                Num_Area++;
                BFS(x, y);
            }
        }
        Answer = Bigger(Answer, Num_Area);
    }
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}