▶실버1
풀이
2차원 bfs문제. 점을 기준으로 탐색하는게 아니라 영역기준이므로 다음과 같은 형태로 정사각형 네 꼭짓점 중 왼쪽 아래를 기준으로 잡는다.
x, y 값이 주어지면 for문으로 해당 범위 내의 arr[x][y]의 값을 true로 바꿔준다. 모든 범위가 주어지고 나면 (0, 0)부터 (n - 1, m - 1)까지 돌며 bfs 실행.
코드
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;
queue <pair<int, int>> q;
int r[4] = { 1, -1, 0, 0 };
int c[4] = { 0, 0, 1, -1 };
bool arr[251][251];
int land;
vector <int> ans;
int bfs(int n, int m) {
int cnt = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + r[i];
int ny = y + c[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (arr[nx][ny] == false) {
arr[nx][ny] = true;
cnt++;
q.push({ nx, ny });
}
}
}
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int m, n, k;
cin >> m >> n >> k;
while(k--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int i = y1; i < y2; i++) {
for (int j = x1; j < x2; j++) {
arr[i][j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == false) {
arr[i][j] = true;
q.push({ i, j });
land++;
int tmp = bfs(n, m);
ans.push_back(tmp);
}
}
}
sort(ans.begin(), ans.end());
cout << land << "\n";
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
11057_오르막수 (0) | 2023.01.04 |
---|---|
2003_수들의 합 2 (0) | 2023.01.02 |
21921_블로그 (0) | 2023.01.01 |
3184_양 (0) | 2022.11.10 |
12847_꿀 아르바이트 (0) | 2022.11.09 |