[백준] 2583 영역 구하기

문제 설명

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

2583번: 영역 구하기

 

크기가 M * N인 모눈종이가 있고, K개의 직사각형을 그릴 때, 직사각형 내부를 제외한 나머지 부분이 몇개인지, 그리고 각 영역의 넓이가 얼마인지 오름차순으로 구하기

 

문제 풀이법

모든 정점을 방문하는 문제이므로 bfs, dfs 모두 사용할 수 있다

 

모눈종이를 가리키는 배열 arr, 방문하였는지 확인하는 배열 visited가 필요하다

1. k개의 직사각형을 입력받아서 각 직사각형의 내부에 해당하는 arr의 좌표값을 1로 입력
   1. 좌측 하단이 (0, 0)이므로 헷갈리기에 좌측 상단을 (0, 0)으로 생각하고 연산을 진행함
   2. 입력된 (x1, y1, x2, y2)를 (x1, n - y1, x2, n - y2)로 변경 (n과 m도 문제와는 다르게 n을 y축, m을 x축으로 변경)
2. (0, 0)부터 visited[y][x]가 0이고, arr[y][x]가 0인 지점을 dfs, bfs를 돌린다
3. 각 영역의 크기가 구해지면 vector에 값을 입력한 후, 오름차순으로 정렬한다
4. 원하는 값을 출력하면 끝!

 

소스 코드

bfs

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

using namespace std;

int arr[101][101] = { 0 };
int visited[101][101] = { 0 };

int dy[4] = { 1, 0, -1, 0};
int dx[4] = { 0, 1, 0, -1};

int n, m, k;

int bfs(int y, int x)
{
    visited[y][x] = 1;
    
    queue<pair<int, int>> q;
    
    q.push({y, x});
    
    int cnt = 0;
    while (!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        
        q.pop();
        cnt++;
        
        for (int i = 0; i < 4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            
            if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] == 1 || arr[ny][nx] == 1)
                continue;
            q.push({ny, nx});
            visited[ny][nx] = 1;
        }
    }
    
    return (cnt);
}

int main()
{
    
    cin >> n >> m >> k;
    
    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2, tmp;
        cin >> x1 >> y1 >> x2 >> y2;
        
        y1 = n - y1;
        y2 = n - y2;
        
        if (y1 > y2)
        {
            tmp = y1;
            y1 = y2;
            y2 = tmp;
        }
        
        if (x1 > x2)
        {
            tmp = x1;
            x1 = x2;
            x2 = tmp;
        }
        for (int j = y1; j < y2; j++)
        {
            for (int p = x1; p < x2; p++)
                arr[j][p] = 1;        
        }
    }
    
    vector<int> v;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0 && visited[i][j] == 0)
            {
                int tmp = bfs(i, j);
                v.push_back(tmp);
                cnt++;
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", cnt);
    for (int i = 0; i < v.size(); i++)
        printf("%d ", v[i]);
    
    
    
    return 0;
}

 

dfs

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

using namespace std;

int arr[101][101] = { 0 };
int visited[101][101] = { 0 };

int dy[4] = { 1, 0, -1, 0};
int dx[4] = { 0, 1, 0, -1};

int n, m, k;

int sum;

void dfs(int y, int x)
{
    if (visited[y][x] == 1)
        return ;
    visited[y][x] = 1;
    sum++;
    
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] == 1 || arr[ny][nx] == 1)
            continue;
        dfs(ny, nx);
    }
}

int main()
{
    
    cin >> n >> m >> k;
    
    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2, tmp;
        cin >> x1 >> y1 >> x2 >> y2;
        
        y1 = n - y1;
        y2 = n - y2;
        
        if (y1 > y2)
        {
            tmp = y1;
            y1 = y2;
            y2 = tmp;
        }
        
        if (x1 > x2)
        {
            tmp = x1;
            x1 = x2;
            x2 = tmp;
        }
        for (int j = y1; j < y2; j++)
        {
            for (int p = x1; p < x2; p++)
                arr[j][p] = 1;        
        }
    }
    
    vector<int> v;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0 && visited[i][j] == 0)
            {
                sum = 0;
                dfs(i, j);
                v.push_back(sum);
                cnt++;
            }
        }
    }
    sort(v.begin(), v.end());
    printf("%d\n", cnt);
    for (int i = 0; i < v.size(); i++)
        printf("%d ", v[i]);
    
    
    
    return 0;
}