[BFS] BOJ 10026 : 적록색약

문제

---

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

---

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

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

 

출력

---

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

 

풀이

---

1. 기본적인 연결요소의 수를 카운트하는 BFS 함수를 만든다.

2. 색맹을 구분해주는 매개변수 able 을 추가한다.

3. 색맹의 경우 R 과 G 의 경우 모두 큐에 넣어 준다.

 

 

코드

---

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <utility>
#include <cstring>

using namespace std;

int cnt1, cnt2;
int check[101][101];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;

void bfs( vector<string> &a,int x,int y, bool able) {
	char color = a[x][y];
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	check[x][y] = 1;
	
	while (!q.empty()) {
		int x1 = q.front().first;
		int y1 = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x1 + dx[k];
			int ny = y1 + dy[k];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (check[nx][ny] == 1) continue;
			if (able == true || color == 'B') {
				if (a[nx][ny] != color) continue;
				check[nx][ny] = 1;
				q.push(make_pair(nx, ny));
			}
			else {
				if (a[nx][ny] == 'B') continue;
				check[nx][ny] = 1;
				q.push(make_pair(nx, ny));


			}
		}

	}

}


int main() {


	cin >> n;
	vector<string> a(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (check[i][j] == 1)continue;
			bfs(a, i, j, true);
			cnt1++;
		}
	}
	cout << cnt1 << ' ';
	memset(check, -1, sizeof(check));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (check[i][j] == 1)continue;
			bfs(a, i, j, false);
			cnt2++;
		}
	}
	cout << cnt2 << '\n';


	return 0;
}