[BOJ] 10026번: 적록색약

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

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력

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

 

---

풀이

📒 DFS (깊이 우선 탐색)

적록색약인 경우 입력받은 그림에서 G를 R로 바꿔 DFS를 이용하여 탐색하면 된다.

 

코드

#include <iostream>
#include <string.h>
using namespace std;

char s[100][100];
int check[100][100] = {0,};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int ans1 = 0;
int ans2 = 0;
int n;

void rgb(int a, int b, char m) {
  check[a][b] = 1;
  for(int i = 0; i < 4; i++) {
    int x = dx[i] + a;
    int y = dy[i] + b;
    if(x<0 || x>=n || y<0 || y>=n) continue;
    else {
      if(s[x][y] == m && !check[x][y]) {
        rgb(x, y, m);
      }
    }
  }
  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> s[i];
  }
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(!check[i][j]) {
        char a = s[i][j];
        rgb(i, j, a);
        ans1++;
      }
    }
  }

  memset(check, 0, sizeof(check));
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(s[i][j] == 'G') s[i][j] = 'R';
    }
  }

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(!check[i][j]) {
        char a = s[i][j];
        rgb(i, j, a);
        ans2++;
      }
    }
  }

  cout << ans1 << " " << ans2;
}

 

결과