[백준 10026] 적록색약

문제 풀이

 

R, G, B라는 영역이 있을 때, 상하좌우로 인접해있는 영역을 구하는 문제입니다.

중요한 점은 적록색약이 아닌 정상인은 R, G, B 구분할 수 있지만 적록색약인 사람은 R과 G를 같은 색깔로 보게 됩니다.

 

먼저 정상인 부터 구합니다. 상하좌우로 탐색하면서 R, G, B 를 구분하면서 전체 영역의 개수를 구합니다.

그런 후에 다시 방문 배열을 초기화한 후 적록색약인 사람은 R과 G를 같이 볼 수 있도록 하며, 똑같이 상하좌우로 탐색하면서 영역의 개수를 구하면 됩니다.

 

탐색 알고리즘은 BFS or DFS 중 하나를 선택해서 구현합니다.

저는 BFS를 이용해서 구현했습니다.

 

아래의 구현에서 적록색약이 아닌 사람과 적록색약인 사람을 구별하기 위해서 파라미터로 ch1, ch2를 선언했습니다.

정상인은 디폴트로 'A' (의미없는 기호)를 넣어서 탐색했고, 적록색약인 사람은 'R'이면 'G'를 'G'이면 'R'을 지정해서 탐색하였습니다.

소스 코드

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

const int dx[] = { 0,0,-1,1 };
const int dy[] = { 1,-1,0,0 };
const int MAX = 101;

int N;
char board[MAX][MAX];
bool visit[MAX][MAX];

void bfs(int x, int y, char ch1, char ch2 = 'A')
{
	queue<pair<int, int> > q;
	q.push({ x,y });
	visit[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (board[nx][ny] == ch1 || board[nx][ny] == ch2)
			{
				if (visit[nx][ny] == false)
				{
					visit[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}
}

void input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < N; j++)
		{
			board[i][j] = s[j];
		}
	}
}

void solve()
{
	input();

	int man = 0, bman = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == false)
			{
				bfs(i, j, board[i][j]);
				man++;
			}
		}
	}

	fill(visit[0], visit[0] + MAX * MAX, false);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == false)
			{
				if (board[i][j] == 'R')
				{
					bfs(i, j, board[i][j], 'G');
				}
				else if (board[i][j] == 'G')
				{
					bfs(i, j, board[i][j], 'R');
				}
				else
				{
					bfs(i, j, board[i][j]);
				}
				bman++;
			}
		}
	}

	cout << man << ' ' << bman << endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}