(백준 알고리즘 문제풀이) 2583번 영역 구하기
by 줌코딩
문제
어떻게 접근할 것인가
- 일단 사각형의 좌표가 주어지면 사각형이 있는 위치를 다 1로 만든다.
- 그리고 나서 쭉 돌면서 빈칸에 대해서 BFS를 진행하여 빈칸 갯수를 찾아서 ans 벡터에 넣어준다.
- 마지막으로 결과를 sort해서 출력하면 끝이다!
코드
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int n, m, k, x1, y1, x2, y2, arr[100][100];
int d[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int main(){
queue<pii> q;
vector<int> ans;
scanf("%d %d %d", &m, &n, &k);
while(k--){
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
for(int i = x1; i < x2; i++){
for(int j = y1; j < y2; j++)arr[i][j] = 1;
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(arr[i][j] == 0){
int cnt = 1;
q.push(pii(i,j));
arr[i][j] = 1;
while(!q.empty()){
int fx = q.front().first, fy = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = fx + d[k][0], ny = fy + d[k][1];
if(nx >= n || ny >= m || nx < 0 || ny < 0)continue;
if(arr[nx][ny])continue;
arr[nx][ny] = 1;
cnt ++;
q.push(pii(nx, ny));
}
}
ans.push_back(cnt);
}
}
}
sort(ans.begin(), ans.end());
int s = ans.size();
printf("%d\n", s);
for(int i = 0; i < s; i++)printf("%d ", ans[i]);
}
느낀점
- 깔끔깔끔 까아아알끔!
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS