백준 - 10026번 : 적록색약 (C++)

풀이 방법 : DFS

간단하게 색약이 아닌 경우, 색약인 경우로 두 번 깊이 우선 탐색을 돌려주면 된다.
입력값이 작으니 2번 돌려도 시간이 충분하다.
구분할 수 있는 색을 만나면 더 이상 탐색을 진행하지 않도록 했고 하나의 탐색이 끝나면 구역의 수를 하나 늘려주는 식으로 구현했다.

#include <iostream>
#include <memory.h>

using namespace std;

int N;

char Paint[101][101] = {};
bool Check[101][101] = {};

int DirX[4] = { 0,0,1,-1 };
int DirY[4] = { 1, -1,0, 0 };

bool DFS(int X, int Y, bool IsWeak)
{
	if (Check[Y][X])
		return false;

	Check[Y][X] = true;

	for (int i = 0; i < 4; ++i)
	{
		int NextX = X + DirX[i];
		int NextY = Y + DirY[i];

		if (NextY < 0 || NextY >= N ||
			NextX < 0 || NextX >= N)
			continue;

		if(Paint[Y][X] == Paint[NextY][NextX])
			DFS(NextX, NextY, IsWeak);

		else
		{
			if (IsWeak)
			{
				if ((Paint[Y][X] == 'R' && Paint[NextY][NextX] == 'G')
					|| (Paint[Y][X] == 'G' && Paint[NextY][NextX] == 'R'))
					DFS(NextX, NextY, IsWeak);
			}
		}
	}

	return true;
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> Paint[i][j];
		}
	}

	int Normal = 0;
	int ColorWeak = 0;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (DFS(i, j, false))
				++Normal;
		}
	}

	memset(Check, 0, 101 * 101);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (DFS(i, j, true))
				++ColorWeak;
		}
	}

	cout << Normal << ' ' << ColorWeak;
}