💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 2104KB Time 0ms Code Length 1278B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int M, N, K;
int field[101][101];
int visited[101][101];
vector<int> vc;
void init() {
cin >> M >> N >> K;
for (int i = 0; i < K; i++) {
int sy, sx;
cin >> sx >> sy;
int ey, ex;
cin >> ex >> ey;
for (int y = sy; y < ey; y++) {
for (int x = sx; x < ex; x++) {
field[y][x] = 1;
}
}
}
}
int bfs(int y, int x) {
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1,0,1 };
int cnt = 1;
queue<pair<int, int>> q;
q.push({ y,x });
while (!q.empty()) {
pair<int, int> now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
if (field[ny][nx] == 1) continue;
if (visited[ny][nx])continue;
visited[ny][nx] = 1;
cnt++;
q.push({ ny,nx });
}
}
return cnt;
}
int main() {
init();
int total_cnt = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (field[i][j] == 1) continue;
if (visited[i][j])continue;
visited[i][j] = 1;
int sum = bfs(i, j);
vc.push_back(sum);
total_cnt++;
}
}
sort(vc.begin(), vc.end());
cout << total_cnt << "\n";
for (auto a : vc) {
cout << a << " ";
}
}
이 코드는 주어진 필드 내에서 직사각형 모양의 영역을 입력받고, 해당 영역을 제외한 나머지 영역을 탐색하여 연결된 영역의 개수를 구하는 BFS 알고리즘을 구현하고 있다.
init() 함수는 필드의 크기와 직사각형의 개수 및 위치를 입력받아 해당 위치에 직사각형이 있는지 표시한다.
bfs() 함수는 주어진 시작 위치에서 상하좌우로 이동하면서 연결된 영역을 탐색하고, 방문한 위치를 표시하며 연결된 영역의 개수를 반환한다.
main() 함수에서는 모든 위치를 탐색하면서 직사각형이 아니고 방문하지 않은 위치에서 bfs() 함수를 호출하여 연결된 영역의 개수를 구하고, 이를 vc 벡터에 저장한다. 마지막으로 vc 벡터를 정렬하고, 총 연결된 영역의 개수와 각 영역의 크기를 출력한다.
