[알고리즘 BFS & DFS 19] COWART

문제

---

소에 대해 잘 알려지지 않은 사실은 소들 눈에는 빨간색과 초록색이 같아보이는 적록색약이라는 것이다. 이 사실은 인간뿐만아니라 소에게도 호소력있는 예술 작품을 만들기 어렵게한다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

copy

RRRBB GGBBB BBBRR BBRRR RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 소는 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 소가 봤을 때와 적록색약이 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에 걸쳐 그림이 주어진다.

 

출력

---

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 소가 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

 

예제 입력

5

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

예제 출력

4 3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
 
const int MAX = 105;
 
char arr[MAX][MAX];
int check[MAX][MAX];
 
int n;
int group = 1;
 
//inside check
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool inside(int x, int y){
  return (x>=0 && x<n) && (y>=0 && y<n);
}
 
void DFS(int x, int y, int cnt, char rgb){
  
  check[x][y] = 1;
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = x + dx[i];
    ny = y + dy[i];
    if(inside(nx,ny) && check[nx][ny]==0 && arr[nx][ny] == rgb){
      DFS(nx,ny, cnt, rgb);
    }
  }
}
 
int main(){
  
  cin>>n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      scanf("\n%c\n",&arr[i][j]);
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(check[i][j]==0){
        DFS(i,j,group,arr[i][j]);
        group++;
      }
    }
  }
  
  //사람이 봤을때 구역
  printf("%d ",group-1);
  
  memset(check,0,sizeof(check));
  group = 1;
  
  //G를 R로 모두 변경
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(arr[i][j]=='G'){
        arr[i][j]='R';
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(check[i][j]==0){
        DFS(i,j,group,arr[i][j]);
        group++;
      }
    }
  }
  
  printf("%d\n",group-1);
  
  
  //테스트 출력
  /*
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      printf("%c",arr[i][j]);
    }
    printf("\n");
  }
  */
  
  return 0;
}