습관처럼
백준 10026 - 적록색약 본문
https://www.acmicpc.net/problem/10026
문제 설명
적록 생맹이므로 'R'와 'G'를 같은 색으로 인식한다 이때 색의 영역이 주어질때 정상일때 보이는 색의 영역의 개수와 그렇지 않을때 보이는 색의 영역의 개수를 각각 구하시오~
접근 방법
BFS 문제이고 정상일때 영역을 구하는 함수와 적록색약일때 보이는 영역을 구하는 함수를 따로 설정하여 풀이했습니다~
코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n,cnt=0,cnt2=0;
char arr[101][101];
bool visit[101][101];
bool visit2[101][101];
int dy[]={1,0,-1,0};
int dx[]={0,-1,0,1};
void normalEyes(int y, int x){
queue<pair<int,int> >q;
q.push(make_pair(y,x));
while(!q.empty()){
int cury = q.front().first;
int curx =q.front().second;
visit[cury][curx]=true;
q.pop();
for(int i=0;i<4;i++){
int ny= cury+dy[i];
int nx= curx+dx[i];
if(ny>=0&&nx>=0&&ny<n&&nx<n){
if(!visit[ny][nx]&&(arr[ny][nx]==arr[cury][curx])){
q.push(make_pair(ny,nx));
visit[ny][nx]=true;
}
}
}
}
cnt++;
}
void greenAbnormalEyes(int y, int x){
queue<pair<int,int> >q2;
q2.push(make_pair(y,x));
while(!q2.empty()){
int cury = q2.front().first;
int curx =q2.front().second;
visit2[cury][curx]=true;
q2.pop();
for(int i=0;i<4;i++){
int ny= cury+dy[i];
int nx= curx+dx[i];
if(ny>=0&&nx>=0&&ny<n&&nx<n){
if(!visit2[ny][nx]){
if(arr[cury][curx]=='B'){
if(arr[ny][nx]==arr[cury][curx]){
q2.push(make_pair(ny,nx));
visit2[ny][nx]=true;
}
}
else{
if(arr[ny][nx]=='R'||arr[ny][nx]=='G'){
q2.push(make_pair(ny,nx));
visit2[ny][nx]=true;
}
}
}
}
}
}
cnt2++;
}
int main(){
cin>>n;
memset(visit,false,sizeof(visit));
memset(visit2,false,sizeof(visit2));
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
if(!visit[i][j]) normalEyes(i,j);
for(int j=0;j<n;j++)
if(!visit2[i][j]) greenAbnormalEyes(i,j);
}
cout<<cnt<<" "<<cnt2;
return 0;
}
funny algorithms ~^0^b
'Algorithms > BOJ' 카테고리의 다른 글
백준 1003 - 피보나치 함수 (0) | 2020.04.05 |
---|---|
백준 9663 - N Queen (0) | 2020.04.03 |
백준 1654 - 랜선 자르기 (0) | 2020.04.01 |
백준 10815 - 숫자 카드 (0) | 2020.03.31 |
백준 11004 - k번째 수 (0) | 2020.03.30 |