#10026 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

골드 5의 문제이다. 계속 dp풀다가 지쳐서 잠깐 dfs/bfs로 넘어와서 한문제 풀어보았다. 이 문제 또한 어렵지 않아서 힘들지 않게 풀었다!

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int n,cnt,cow;
char map[101][101];
int visited[101][101];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<pair<int,int>> q;

void bfs(int x,int y,char c){
  q.push(make_pair(x,y));
  visited[x][y]=1;
  while(!q.empty()){
    x=q.front().first;
    y=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(0<=nx && nx<n && 0<=ny && ny<n){
        if(map[nx][ny]==c && visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
        }
      }
    }
  }
}

void cowbfs(int x,int y,char c){
  q.push(make_pair(x,y));
  visited[x][y]=1;
  while(!q.empty()){
    x=q.front().first;
    y=q.front().second;
    q.pop();
    for(int k=0;k<4;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(0<=nx && nx<n && 0<=ny && ny<n){
        if(c=='R' || c=='G'){
          if(map[nx][ny]=='R' || map[nx][ny]=='G'){
            if(visited[nx][ny]==0){
              q.push(make_pair(nx,ny));
              visited[nx][ny]=1;
            }
          }
        }
        else if(c=='B'){
          if(map[nx][ny]==c && visited[nx][ny]==0){
            q.push(make_pair(nx,ny));
            visited[nx][ny]=1;
          }
        }
      }
    }
  }
}

int main()
{
  freopen("input.txt","r",stdin);
  cin>>n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>map[i][j];
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(map[i][j]=='R' && visited[i][j]==0){
        bfs(i,j,'R');
        cnt++;
      }
      
      if(map[i][j]=='G' && visited[i][j]==0){
        bfs(i,j,'G');
        cnt++;
      }
      
      if(map[i][j]=='B' && visited[i][j]==0){
        bfs(i,j,'B');
        cnt++;
      }
    }
  }
  memset(visited,0,sizeof(visited));
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(map[i][j]=='R' && visited[i][j]==0){
        cowbfs(i,j,'R');
        cow++;
      }

      if(map[i][j]=='G' && visited[i][j]==0){
        cowbfs(i,j,'G');
        cow++;
      }
      
      if(map[i][j]=='B' && visited[i][j]==0){
        cowbfs(i,j,'B');
        cow++;
      }
    }
  }

  cout<<cnt<<" "<<cow<<'\n';
}

코드가 생각보다 길구나;;!

이 문제의 핵심 내용은 입력으로 받은 R과 G를 어떻게해야 같은 것으로 처리 할까 이다.

일단 다른 문제들과 다르게 문자를 입력 받으므로 map배열을 char 형으로 선언해주고 그래프를 돌기위한 다른 배열들도 선언해주었다. 원래는 bfs라는 하나의 함수 안에 색맹일때의 결과와 정상일때의 결과를 같이 계산 해주는 기능을 같이 넣으려 했으나 코드를 짜다보니 쉽지않음을 직감하고 아예 두개의 bfs함수로 나누어버렸다. 하나는 정상일때를 계산해주는 bfs, 나머지 하나는 색맹일때를 계산해주는 bfs (문제를 영어로 보니까 제목이 'Cow Arts' 길래 cowbfs라고 했다) 로 만들었다. 

bfs함수 내에서는 일반적인 방법으로 그래프 순회를 진행하였고, x와 y좌표 이외에 색깔을 parameter로 받아서 구성했다. 이중 포문을 돌면서 R일때 bfs, G일때... ,B일때.... 이런식으로 했다.

 

문제는 cowbfs함수이다. 고민을 좀 해봤는데 생각보다 쉬웠다. 다음칸으로 진행한 nx와 ny가 범위 안에 있을때, 파라미터로 입력받은 색깔이 R이거나 G이면 이를 같이 생각하는 코드를 짰다.

 

마지막에 main함수 내에서 cowbfs를 돌릴때 

if(map[i][j]=='G' && visited[i][j]==0){
    cowbfs(i,j,'G');
    cow++;

}

 

이 부분을 안 넣었었다. R에서 cowbfs를 돌렸을때 G까지 커버가 가능하니 괜찮을 것이라고 생각했었는데,

RRR

BBB

GGG

와 같이 R과 G가 떨어져있는 경우에는 G를 탐색하지 않기때문에 틀린 코드였다. 이거 실수 하나 정도 했당 ㅎㅎ;