백준 2583_영역 구하기

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

2583번: 영역 구하기

 

 접근

 입력과 함계 영역을 색칠한다

 

 for y <- (y1 ~ y2-1)

    for x <- (x1 ~ x2-1)

        map[y][x] = 1

 

 bfs 함수로 빈칸의 넓이를 구한다

 bfs 탐색 호출 횟수로 사각형의 갯수를 구한다

 

 예시에선 y가 감소하는 방향이 더 큰 숫자가 되는

 4 사분면 이지만 사각형의 개수를 구하는데는 관계가 없으므로

 1 사분면이라 생각하고 문제 풀이를 진행 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 101

using namespace std;
int dy[4] {-1, 1, 0, 0};
int dx[4] {0, 0, -1, 1};
struct pos {int y, x;};
int map[MAX][MAX];
int n, m, k;
bool visited[MAX][MAX];

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

int main(int argc, const char * argv[]) {
    int x1, y1, x2, y2;
    
    scanf("%d %d %d", &n, &m, &k);
    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;
            }
        }
    }
    
    vector<int> ret;
    
    for(int y = 0 ; y < n ; y++){
        for(int x = 0; x < m ; x++){
            if(visited[y][x] || map[y][x]==1)continue;
            ret.push_back(bfs(y, x));
            
        }
    }
    sort(ret.begin(), ret.end());
    printf("%d\n", (int)ret.size());
    for(int area : ret){
        printf("%d ", area);
    }
    printf("\n");
    
    
    
    return 0;
}