[2583번] 영역 구하기

문제 출처 :

https://www.acmicpc.net/problem/2583

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

전형적인 BFS문제이다. 

처음에 입력받아 채워지는 직사각형은 -1로 설정하고 BFS를 돌리며 

현재 map이 아직 0이라면 그 위치를 탐색하고 0이 아닌 다른 값이라면 

-1 혹은 이미 방문한 값이니 들리지 않도록 하여 문제를 해결한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int map[102][102];
int cnt = 1;
 
typedef pair<int, int> pii;
queue <pii> q;
vector<int> ans;
 
int main()
{
    int n, m, k;
    int x1, y1, x2, y2;
    int get = 0;
    scanf("%d %d %d", &n, &m, &k);
 
    // 미리 칠해지는 영역을 -1로 설정
    for (int i = 0; i < k; i++)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
 
        for (int y = y1; y < y2; y++)
            for (int x = x1; x < x2; x++)
                map[y][x] = -1;        
    }
    
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < m; x++)
        {
            // map에 이미 값이 존재한다면
            if (map[y][x])
                continue;
 
            q.push(pii(y, x));
 
            // BFS
            while (!q.empty())
            {
                int herex, herey;
 
                herey = q.front().first;
                herex = q.front().second;
 
                // 맵에 이미 값이 존재한다면
                if (map[herey][herex])
                {
                    q.pop();
                    continue;
                }
 
                map[herey][herex] = cnt;
                get++;
 
                q.pop();
 
                if (herey - 1 >= 0 && map[herey - 1][herex] == 0)
                    q.push(pii(herey - 1, herex));
 
                if (herey + 1 < n && map[herey + 1][herex] == 0)
                    q.push(pii(herey + 1, herex));
 
                if (herex - 1 >= 0 && map[herey][herex - 1] == 0)
                    q.push(pii(herey, herex - 1));
 
                if (herex + 1 < m && map[herey][herex + 1] == 0)
                    q.push(pii(herey, herex + 1));
            }
 
            // 다음 영역의 번호 지정 및 get(넓이) 저장
            cnt++;
            ans.push_back(get);
            get = 0;
        }
 
 
    }
    
    // 넓이 오름차순 정렬 
    sort(ans.begin(), ans.end());
 
    printf("%d\n", cnt - 1);
 
    for (int i = 0; i < cnt - 1; i++)
        printf("%d ", ans[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>