문제링크 : https://www.acmicpc.net/problem/2583
이 문제는 2차원 좌표계에서의 영역을 구하는 문제 입니다.
우선 문제에서 주어진 직사각형의 크기대로 visited배열에 넣어주어야 합니다.
직사각형들을 처리한 후(visited를 true)로 한 후 visited가 false인 부분마다 dfs를 시작해주면 됩니다.
소스코드 ;
이 문제는 2차원 좌표계에서의 영역을 구하는 문제 입니다.
우선 문제에서 주어진 직사각형의 크기대로 visited배열에 넣어주어야 합니다.
직사각형들을 처리한 후(visited를 true)로 한 후 visited가 false인 부분마다 dfs를 시작해주면 됩니다.
소스코드 ;
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
65
66
67
|
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int N, M, K;
int visited[100][100];
int num;
int area;
pair<int, int> direction[4]{ {1,0},{0,1},{-1,0},{0,-1} };
void DFS(int x, int y) {
if (x < 0 || y < 0 || x >= N || y >= M) {
return;
}
if (visited[x][y] == false) {
visited[x][y] = true;
area++;
for (int i = 0; i < 4; i++) {
int dx = x + direction[i].first;
int dy = y + direction[i].second;
DFS(dx, dy);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> M >> N >> K;
// 직사각형을 visited로 변환해줌.
for (int i = 0; i < K; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int j = y1; j < y2; j++) {
for (int k = x1; k < x2; k++) {
visited[k][j] = true;
}
}
}
// 아직 방문하지 않은곳을 dfs로 탐색하며 넓이를 구한다.
vector<int> areas;
for (int y = 0; y < M; y++) {
for (int x = 0; x < N; x++) {
if (visited[x][y] == false) {
area = 0;
DFS(x, y);
areas.push_back(area);
num++;
}
}
}
cout << num << endl;
// 넓이를 오름차순으로 정렬한다.
sort(areas.begin(), areas.end());
for (int i = 0; i < areas.size(); i++) {
cout << areas[i] << ' ';
}
}
| cs |
댓글
댓글 쓰기