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

2583번 : 영역 구하기

---

문제 )

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

 

 

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

 

 

출력 :

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

 

 

 

 

 

 

 

풀이)

습관적으로 BFS를 하다보니 최단거리를 구하 듯이 문제를 풀어버려서

 

정답을 찾는데 좀 오래 걸렸다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int m, n, k, temp;
vector<vector<int>> vec;
vector<vector<int>> visited;
vector<int> answer;
 
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
 
void bfs(int a, int b)
{
    visited[a][b] = 1;
    int t = 1;
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        // 사방 탐색
        for (int i = 0; i < 4; i++)
        {
            int x_dx = x + dx[i];
            int y_dy = y + dy[i];
 
            if ((-1 < x_dx && x_dx < m) &&    // 1. 모눈종이 안의 범위
                (-1 < y_dy && y_dy < n) && 
                (vec[x_dx][y_dy] == 0) &&    // 2. 작사각형 내부 제외
                (visited[x_dx][y_dy] == 0))    // 3. 방문하지 않은 곳
            {
                q.push(make_pair(x_dx, y_dy));
                // 영역의 넓이
                t++;
                visited[x_dx][y_dy] = t;
            }
        }
    }
    
    answer.push_back(t);
}
 
int main()
{
    cin >> m >> n >> k;
 
    // 모눈종이 그리기 
    vec.assign(m, vector<int>(n, 0));
    visited.assign(m, vector<int>(n, 0));
 
    // vec에 직사각형 그리기
    int a, b, c, d;
    for (int i = 0; i < k; i++)
    {
        cin >> a >> b >> c >> d;
        for (int j = b; j < d; j++)
        {
            for (int k = a; k < c; k++)
            {
                vec[j][k] = 1;
            }
        }
    }
 
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (visited[i][j] == 0 && vec[i][j] == 0)
            {
                bfs(i, j);
                temp++;
            }
        }
    }
 
    cout << temp << "\n";
    sort(answer.begin(), answer.end());
    for (auto& ele : answer) cout << ele << " ";
 
    return 0;
}
 

---

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

2583번: 영역 구하기