[백준-10026] 적록 색약
in Coding Test on 백준
DFS 알고리즘을 2개를 써보면 되지않을까
Code
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 101;
int N, answer;
char RGB[MAX][MAX];
bool check[MAX][MAX];
int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
void dfs1(int y, int x) {
if (check[y][x]) return;
check[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;
if (RGB[y][x] == RGB[ny][nx]) {
dfs1(ny, nx);
}
}
}
void dfs2(int y, int x) {
if (check[y][x]) return;
check[y][x] = true;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if (nx<0 || nx>N - 1 || ny<0 || ny>N - 1) continue;
if (RGB[y][x] == RGB[ny][nx]) {
dfs1(ny, nx);
}
}
}
int solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!check[i][j]) {
dfs1(i, j);
answer++;
}
}
}
return answer;
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%s", RGB[i]);
}
int ans1 = solve();
memset(check, 0, sizeof(check));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (RGB[i][j] == 'G')
RGB[i][j] = 'R';
}
}
answer = 0;
int ans2 = solve();
printf("%d %d", ans1, ans2);
return 0;
}