[백준/BOJ] 백준 10026번 : 적록색약

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

10026번: 적록색약

적록색약이 아닌 사람이 (x, y)가 rgb색깔인 점을 볼 때 보는 구역을 bfs를 통해 체크하고, 적록색약인 사람이 (x, y)가 rgb색깔인 점을 볼 때 보는 구역을 bfs를 통해 체크하는 방법으로 적록색약이 아닌 사람이 구별한 구역의 수와, 적록색약인 사람이 구별한 구역의 수를 구한다

 

코드

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

int n;
vector<string> board;
int discoverd1[100][100];
int discoverd2[100][100];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//적록색약이 아닌 사람이 (x,y)가 rgb색깔인 점을 볼때 보는 구역 체크
//(x,y)를 시작으로 해당하는 구역을 bfs한다
void Solve1(int x, int y, char rgb)
{
	pair<int, int> start = make_pair(x, y);
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second+dx_dy[i][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discoverd1[there.first][there.second] == 0 && board[there.first][there.second] == rgb)
			{
				discoverd1[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}
}

//적록색약인 사람이 (x,y)가 rgb색깔인 점을 볼때 보는 구역 체크
//(x,y)를 시작으로 해당하는 구역을 bfs한다
void Solve2(int x, int y, char rgb)
{
	pair<int, int> start = make_pair(x, y);
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

			//rgb가 'R'일때 인접하는 'G'도 같은 구역이고, 'G'일때 인접하는 'R'도 같은 구역이다
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && discoverd2[there.first][there.second] == 0 && (board[there.first][there.second] == rgb || rgb=='R'&&board[there.first][there.second] == 'G' || rgb == 'G'&& board[there.first][there.second] == 'R'))
			{
				discoverd2[there.first][there.second] = 1;
				q.push(there);
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;
	int num1 = 0;
	int num2 = 0;

	memset(discoverd1, 0, sizeof(discoverd1));
	memset(discoverd2, 0, sizeof(discoverd2));

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			//적록색약이 아닌 사람이 발견한 구역이 아닐때
			if (discoverd1[i][j] == 0)
			{
				num1++;
				Solve1(i, j, board[i][j]);
			}

			//적록색약인 사람이 발견한 구역이 아닐때
			if (discoverd2[i][j] == 0)
			{
				num2++;
				Solve2(i, j, board[i][j]);
			}
		}

	cout << num1 << " " << num2;

	return 0;
}