2583번 영역 구하기 BFS 큐 벡터

이 문제는 BFS를 연습하기 가장 좋은 문제인것 같다.  오랜만에 넣자마자 성공..

문제를 풀면서 느낀건데 BFS와 큐 벡터등 기초적인 내용을 잘 익힐수있는 문제라고 생각한다.

문제 예시가 너무 잘나와있어서 문제 해석에는 별로 어려움이 없었다.

풀이과정을 대충 설명하자면

우선 M x N 의 칸을 배열로 매칭시켜야 한다. 그리고 나서 각 나눠진 영역에 대해서 BFS를 돌려야 한다. DFS도 해보진 않았지만 시간제한이 1초이기때문에 왠지 시간초과가 날것같지만 해보진 않았다.

DFS같은경우에는 모든 경우를 탐색할수있지만 한곳을 계속해서 파내려가므로 시간이 오래걸릴수있다는 단점이 있다. 그래서 이문제는  BFS 로 접근하는게 맞는것 같다.

우선 정사각형을 2차원 배열에 맵핑 시켜야 하는데, 아래 코드가 그 코드이다.

    for(int i=0; i<k; i++)

    {

        cin>>x1>>y1>>x2>>y2;

        for(int p=y2-1; p>=y1; p--)

        {

            for(int q=x2-1; q>=x1; q--)

            {

                rec[p][q] = 0;

            }

        }

        

    } //정사각형 범위 0으로 만들기

뭐 이건 조금만 보면 이해할수 있을거라 생각한다. 정사각형이 차지하는 칸을 0으로 나타낸 것일 뿐이다. 다만

주의할점이 하나있는데

문제에서 보면 좌하단이 0,0이고 우측상단이 7,5이다 하지만 우리는 2차원 배열을 사용할것이므로 좌상단을 0,0으로 우하단을 7,5로 사용해야 한다.

나는 그래서 칸을 180도 뒤집어서 좌하단이 좌상단이 되고 우상단이 우하단이 되게끔 만들었다. 그렇게 만들더라도 결국에는 각각의 영역의 넓이와 영역의 개수는 똑같다. 

그렇게 생각을하고 코드를 짜면 아래와 같이 나온다.

0으로 되있는 부분이 정사각형이 차지하는 부분이고 -1이 뜻하는 바는 아직 그곳이 탐색되지 않았다는 것이다. 탐색이 되고 나서는 저 부분들이 1로 바뀌게 될것이다.

그리고 나서 1의 개수를 세면 우리는 영역의 넓이를 구할수 있다.

    for(int i=0; i<m; i++)

    {

        for(int j=0; j<n; j++)

        {

            if(rec[i][j] == -1)

                bfs(i,j);

        }

    }

이 코드처럼 M x N 의 칸을 모두 검색하면서 -1이 있는 부분을 탐색한다 위의 그림에서 예를 들자면 0,0에서 -1이므로 bfs(0,0) 이 실행 될것이고 그 함수 내부적으로 bfs를 사용하므로 0으로 감싸진 부분이 모두 1로 변하게 될것이다. 그럼 반복문의 그다음 반복에서 i=0 j=1일때는 이미 bfs함수때문에 rec[0][1]이 1이 되어있으므로

또다시bfs를 하지 않게 된다. 대충 이런 방식으로 동작하고 각영역의 크기가 얼마이고 영역의 개수는 몇개인지는 bfs함수 내에서 센다.

전체 코드

#include <iostream>
#include <memory.h>
#include <queue>
#include <algorithm>
using namespace std;
int rec[101][101];
queue<int> xque;
queue<int> yque;
vector<int> subsum;
int a[4] = {0,1,0,-1};
int b[4] = {1,0,-1,0};
int m,n,k;
int area=0;
 
void bfs(int x,int y)
{
    int sum =0;
    rec[x][y] = 1;
    xque.push(x);
    yque.push(y);
    
    while(xque.size()>0)
    {
        int x = xque.front();
        int y = yque.front();
        xque.pop();yque.pop();
        
        sum++;
        
        for(int i=0; i<4; i++)
        {
            int nextX = x + a[i];
            int nextY = y + b[i];
            
            if(nextX >=0 && nextX < m && nextY >=0 && nextY < n && rec[nextX][nextY] == -1)
            {
                rec[nextX][nextY] = 1;
                xque.push(nextX);
                yque.push(nextY);
            }
        }
    }
    subsum.push_back(sum);
    area++;
    
}
 
int main()
{
    int x1,y1,x2,y2;
    memset(rec,-1,sizeof(rec));
    cin>>m>>n>>k;
    
    for(int i=0; i<k; i++)
    {
        cin>>x1>>y1>>x2>>y2;
        for(int p=y2-1; p>=y1; p--)
        {
            for(int q=x2-1; q>=x1; q--)
            {
                rec[p][q] = 0;
            }
        }
        
    } //정사각형 범위 0으로 만들기
    
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(rec[i][j] == -1)
                bfs(i,j);
        }
    }
//    
//    for(int i=0; i<m; i++)
//    {
//        for(int j=0; j<n; j++)
//        {
//            printf("%2d ",rec[i][j]);
//        }
//        cout<<endl;
//    }
    
    cout<<area<<endl;
    sort(subsum.begin(),subsum.end());
    for(int i=0; i<subsum.size(); i++)
    {
        printf("%d ",subsum[i]);
    }
    
    
    return 0;
}