영역구하기(백준)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int m, n, k;
int iResult(0);

int Map[101][101] = { 0, };
bool Chk[101][101] = { false, };
int DirX[] = { -1,0,1,0 };
int DirY[] = { 0,-1,0,1 };


vector<int> vDanji;



void BFS(int x, int y)
{
    queue<pair<int,int>> qTemp;
    iResult++;
    Chk[x][y] = true;//방문기록 남기고
    qTemp.push(make_pair(x,y));//하나 집어넣고

    while (!qTemp.empty())
    {
        x = qTemp.front().first;
        y = qTemp.front().second;
        qTemp.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + DirX[i];
            int ny = y + DirY[i];
            if ((nx >= 0) && (nx < m) && (ny >= 0) && (ny < n))
            {
                if ((Chk[nx][ny] == false) && (Map[nx][ny] == 0))
                {
                    iResult++;
                    Chk[nx][ny] = true;//방문기록 하고서 
                    qTemp.push(make_pair(nx,ny));//큐에 다시 집어넣는다. 
                }
            }
        }
    }
}

bool cmp(int a, int b)
{
    return a < b;
}



int main()
{
  

    
    cin >> m >> n >> k; //행과 열

    for (int i = 0; i < k; i++) { //사각형 영역을 1로 주기.

        int startX, startY, endX, endY;
        cin >> startX >> startY >> endX >> endY;

        for (int j = startX; j < endX; j++) {
            for (int t = startY; t < endY; t++) {
                Map[t][j] = 1;//주어진 사각형을 1로 만들어준다.
            }
        }
    }


    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((Map[i][j]==0)&&(Chk[i][j] == false))
            {

                BFS(i, j);
                vDanji.emplace_back(iResult);
                iResult = 0;
            }
        }
    }

    sort(vDanji.begin(), vDanji.end(), cmp);

    cout << (int)vDanji.size() << endl;
    for (int i = 0; i < vDanji.size(); i++)
    {
        cout << vDanji[i] << " ";
    }

    return 0;
}

이문제 풀때
기존의 문제들은 1을 찾는 거였는데,
이문제는 0을 찾아서 너비를 구하는 거였음.
문제 의도파악 재대로 하고 풀기.
BFS를 하며, 영역 잘린 부분처리.
(포문 두번돌리며 vDanji활용하기)Skill익히기.