[백준 알고리즘]/[C++]
10026번 적록색약 | DFS | 백준 10026 C++ 코드
말하는펭귄
2021. 2. 11. 20:52
728x90
반응형
이번 포스팅은 백준 10026번 적록색약입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
기본 알고리즘
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
//백준10026 적록색약
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int N;
const int MAX = 101;
char map[MAX][MAX];
bool visited[MAX][MAX] = { 0, };
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
void DFS_R(int y, int x) {
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
if (map[ny][nx] == 'R' && visited[ny][nx] == 0) {
visited[ny][nx] = true;
DFS_R(ny, nx);
}
}
}
void DFS_G(int y, int x) {
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
if (map[ny][nx] == 'G' && visited[ny][nx] == 0) {
visited[ny][nx] = true;
DFS_G(ny, nx);
}
}
}
void DFS_B(int y, int x) {
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N)
continue;
if (map[ny][nx] == 'B' && visited[ny][nx] == 0) {
visited[ny][nx] = true;
DFS_B(ny, nx);
}
}
}
void resetVisit() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visited[i][j] = 0;
}
}
}
int main() {
/*입력 받기*/
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%1s", &map[i][j]);
}
}
int cntR = 0; //R구역 개수
int cntG = 0; //G구역 개수
int cntB = 0; //B구역 개수
int notColorBlind = 0; //적록색약 아닌 사람이 보는 구역의 수
/*R,G,B 각각 DFS*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 'R' && visited[i][j] == 0) {
DFS_R(i, j);
cntR++;
}
if (map[i][j] == 'G' && visited[i][j] == 0) {
DFS_G(i, j);
cntG++;
}
if (map[i][j] == 'B' && visited[i][j] == 0) {
DFS_B(i, j);
cntB++;
}
}
}
notColorBlind = cntR + cntG + cntB;
/*visited 초기화*/
resetVisit();
cntR = 0; //R구역 개수 초기화
int colorBlind = 0; //적록색약인 사람이 보는 구역의 수
/*map에서 G를 전부 R로 변환*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 'G') {
map[i][j] = 'R';
}
}
}
/*R로 변환된 G를 합한 R 구역 DFS*/
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 'R' && visited[i][j] == 0) {
DFS_R(i, j);
cntR++;
}
}
}
colorBlind = cntR + cntB;
cout << notColorBlind << " " << colorBlind;
}
|
cs |
728x90
반응형