BFS
를 이용한 간단한 문제이다. 문제에서 구해야하는 답은 적록색약이 아닌 사람과 적록색약인 사람이 봤을 때의 구역의 수이다. 그렇기에 BFS
와 BFS2
함수 두가지를 사용하여 답을 구하였다. BFS2
함수는 적록색약을 대상으로하는 함수이기때문에 처음 배열을 입력받을 때 G 구역을 R로 바꿔준 문자열 B
를 사용하여 BFS
를 돌려주었다. 두 함수 모두 방문한 구역은 'E'로 바꿔주어 visit
배열 없이 방문 여부를 확인해 주었다.
간단한 문제였기에 큰 어려움이 없었다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N;
string A[100];
string B[100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
void bfs(int a, int b, char c) {
queue<pair<int, int>> q;
A[a][b] = 'E';
q.push({ a,b });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
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 (A[ny][nx] != c) continue;
A[ny][nx] = 'E';
q.push({ ny,nx });
}
}
}
void bfs2(int a, int b, char c) {
queue<pair<int, int>> q;
B[a][b] = 'E';
q.push({ a,b });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
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 (B[ny][nx] != c) continue;
B[ny][nx] = 'E';
q.push({ ny,nx });
}
}
}
void solution() {
int n = 0, n2 = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] == 'R' || A[i][j] == 'G' || A[i][j] == 'B') {
n++;
bfs(i, j, A[i][j]);
}
if (B[i][j] == 'R' || B[i][j] == 'B') {
n2++;
bfs2(i, j, B[i][j]);
}
}
}
cout << n << " " << n2 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
string a;
cin >> a;
A[i] = a;
B[i] = a;
for (int j = 0; j < N; j++) {
if (B[i][j] == 'G') {
B[i][j] = 'R';
}
}
}
solution();
return 0;
}