문제링크 : https://www.acmicpc.net/problem/10026
이 문제는 Flood Fill 문제입니다.
다만, 영역을 1번만 찾는것에서 끝나는게 아닌 적록색약까지 고려하여 2번 찾아야 하는 문제 입니다.
DFS로 풀었으며, 적록색약을 고려하기 위해 정상인 영역을 구한 후 녹색을 적색으로 바꿔서 다시한번 DFS로 구하였습니다.
소스코드 :
이 문제는 Flood Fill 문제입니다.
다만, 영역을 1번만 찾는것에서 끝나는게 아닌 적록색약까지 고려하여 2번 찾아야 하는 문제 입니다.
DFS로 풀었으며, 적록색약을 고려하기 위해 정상인 영역을 구한 후 녹색을 적색으로 바꿔서 다시한번 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int v[101][101]{ -1 };
bool visited[101][101]{ false, };
pair<int, int> direction[4]{ {1,0},{0,1}, {-1,0},{0,-1} };
void DFS(int x, int y, int color) {
if (x < 0 || y < 0 || x >= n || y >= n) {
return;
}
if (visited[x][y] == false && v[x][y] == color) {
visited[x][y] = true;
if (v[x][y] == 71) {
v[x][y] = 82;
}
for (int i = 0; i < 4; i++) {
int dx = x + direction[i].first;
int dy = y + direction[i].second;
DFS(dx, dy, color);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin.clear();
cin.ignore();
for (int i = 0; i < n; i++) {
string str;
getline(cin, str);
for (int j = 0; j < n; j++) {
v[i][j] = str[j];
}
}
int r, g, b;
r = g = b = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == false ) {
DFS(i, j, v[i][j]);
if (v[i][j] == 82) {
r++;
}
else if (v[i][j] == 71) {
g++;
v[i][j] = 82;
}
else {
b++;
}
}
}
}
cout << r + g + b;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = false;
}
}
r = g = b = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == false) {
DFS(i, j, v[i][j]);
if (v[i][j] == 82) {
r++;
}
else if (v[i][j] == 71) {
g++;
}
else {
b++;
}
}
}
}
cout << ' ' <<r +g+b;
}
| cs |
댓글
댓글 쓰기