[ 백준 2583 ] 영역 구하기 (C++)

백준의 영역구하기(2583) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 모눈종이의 크기와 사각형의 갯수를 입력받는다.

- 입력받은 사각형의 갯수만큼 사각형이 있는 좌표점을 입력받는다.

- 사각형이 있는 부분은 모눈종이에서 색깔이 칠해진다.

- 사각형을 모두 만들고 난 후에, 색칠하지 않은 영역이 총 몇개인지, 그리고 그 영역들의 크기가 얼마인지 출력시킨다.

   - 여기서 영역이라고 하는 것은, 상하좌우 중 한 방향으로라도 칠해지지 않은(사각형이 아닌) 연결된 부분을 의미한다.

[ 문제풀이 ]

1) 전체 모눈종이(맵)의 가로길이와 세로길이, 그리고 사각형의 갯수를 입력받는다.

2) 그리고 사각형의 왼쪽아래 좌표와, 오른쪽 위 좌표를 입력받게 되는데, 왼쪽아래부터 오른쪽 위 까지는 모두 사각형으로써

   색을 칠하게된다. 

   2-1) 예를 들어, 왼쪽아래 좌표로 (2, 2)를 입력받고 오른쪽 위 좌표로 (1, 3)을 입력받게되면 실제 구현할 때 맵 상으로는

          (2, 2), (2, 3), (1, 2), (1, 3) 이 4개의 좌표가 사각형으로 칠해지게 되는 것이다.

3) 맵이 우리가 평소에 하는 맵의 형태와 다르기 때문에 주의해야 한다. 왼쪽위가 (0,0)이 아닌, 왼쪽 아래가 ( 0,0)이고,

   오른쪽 아래가 (N, M)이 아닌 오른쪽 위가 (N, M)이 된다.

   ( * 맵의 가로축 , 세로축을 관리하는 것은 사람 마다 다름 ! 자기가 편한 기준으로 사용하면 됨 ! * )

   3-1) 따라서, 입력받는 사각형의 좌표도 있는 그대로를 맵에 설정해주는 것이 아닌, 바뀐 맵에 맞춰서 설정해 주어야 한다.

4) 바뀐 맵에 대해서 구체적으로 알아보면...

( 먼저 본인은 행렬과 같은 방식으로 x, y축을 계산한다. (0,0)에서 오른쪽으로 한칸 움직이면 y가 증가하여  (0,1)이 되고, 

  아래쪽으로 한칸 움직이면 x가 증가하여 (1,0)이 되는 방식 )

   가장 왼쪽 열이 0이고, 가장 오른쪽 열이 N인 것은 우리가 평소에 하는 맵과 같다.

   바뀐 것은, 행이다. 가장 위쪽 행이 M이 되고, 가장 아래 행이 0이 된다.

   그럼 우리가 평소에 하던 맵을 기준으로 문제의 예제입력인 [ (0,2) , (4,4) ] 를 입력받아보자. 본인은 위에서 말했다시피,

   문제와 입력받는 방식이 반대이다. 문제에서는 y축으로 2칸 증가한 (0,2)를 의미하지만, 본인에게는 세로축 증가를 x값 

   증가로 기준으로 두었기 때문에 입력 자체를 반대로 받았다. 즉 (x, y) = (0, 2)가 아닌 (y, x) = (0, 2) 을 받은 것이다

   이 문제에서 (0, 2)로 입력받은 것은 (2, 0)을 입력받은 것을 의미하고, (2, 0)의 좌표는 실제 (3, 0)의 좌표에 위치한다.

   그 다음좌표인 (4, 4)로 입력받은 것은 (4, 4)를 입력받은 것을 의미하고, (4, 4)의 좌표는 실제 (1, 4)의 좌표에 위치한다.

   즉, x좌표만 x = M - x 로 값을 바꿔주게 되면, 문제에서 요구하는 대로 입력받을 수 있다.       

   4-1) 위와 같이 입력을 받고 난 후에, 이제 사각형으로 표시만 해주면 된다. 즉 (M-x, y), (M-xx, yy) 이 두 좌표를 이용해

         저 사이에 있는 모든 좌표를 사각형으로 표시해주면 된다.

         본인 같은 경우에는 맵을 입력받고, 모든 값을 0으로 초기화 시킨 후, 사각형에는 1을 표시해 두었다.

5) 이제 맵을 입력받았으니, 본격적으로 영역의 갯수와 각 영역의 크기를 구해보자. 먼저, 영역의 갯수는 BFS 함수가 실행되

   는 횟수와도 같다. 

   - 그 이유는, BFS에서는 상하좌우를 탐색하면서 사각형이 아닌 지점에 대해서 계속 탐색을 할 것이고, 더 이상 탐색할 수

     없을 때, 탐색이 종료될 것이다. 즉, 특정 0인 지점에서 BFS를 호출하고, 탐색이 종료되면 영역이 1개 ++ 되는 것이다.

   5-1) BFS안에서는 그 영역의 넓이만 Count 해주면 된다. Queue를 생성할 때, 변수 하나를 더 같이 넣어서 생성해서 

         Count해줘도 되고, 또 다른 변수를 만들어서 Count를 해줘도 된다. 

   5-2) 영역의 넓이를 관리하는 방법에 대해서 설명하자면, 본인은 Vector를 하나 만들어서 사용했다.

         BFS를 돌리면서 넓이를 Count한 변수를 Vector에 넣어주었다. 영역을 탐색할 때 마다, 그 넓이를 Vector에 넣어주었

         다. 모든 영역에 대한 탐색이 끝났다면, Vector를 Sorting시켜서, 문제에서 요구하는 대로 오름차순으로 정렬하였고

         벡터의 Size만큼 출력시켜 주었다.

[ 소스코드 ]

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int M, N, K, Area_Num;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<int> Area_Size;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
}
 
void CheckInMap(int y, int x, int yy, int xx)
{
    x = M - x;
    xx = M - xx;
    for (int i = y; i < yy; i++)
    {
        for (int j = xx; j < x; j++)
        {
            MAP[j][i] = 1;
        }
    }    
}
 
void Input()
{
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x, y, xx, yy;
        cin >> y >> x >> yy >> xx;
        CheckInMap(y,x,yy,xx);
    }
 
    //for (int i = 0; i < M; i++)
    //{
    //    for (int j = 0; j < N; j++)
    //    {
    //        cout << MAP[i][j] << " ";
    //    }
    //    cout << endl;
    //}
}
 
void BFS(int a, int b)
{
    int Size = 1;
    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 < M && ny < N)
            {
                if (Visit[nx][ny] == false && MAP[nx][ny] == 0)
                {
                    Q.push(make_pair(nx, ny));
                    Visit[nx][ny] = true;
                    Size++;
                }
            }
        }
    }
    Area_Size.push_back(Size);
}
 
void Solution()
{
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] == 0 && Visit[i][j] == false)
            {
                Area_Num++;
                BFS(i, j);
            }
        }
    }
 
    cout << Area_Num << endl;
    sort(Area_Size.begin(), Area_Size.end());
    for (int i = 0; i < Area_Size.size(); i++)
    {
        cout << Area_Size[i] << " ";
    }
    cout << endl;
}
 
void Solve()
{
    Initialize();
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}