[BFS] 적록색약

예제 입력 1

5

RRRBB

GGBBB

BBBRR

BBRRR

RRRRR

예제 출력 1

4 3

 

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

10026번: 적록색약

- 동일한 색깔끼리 BFS를 이용하여 그룹으로 묶는다.

- 일반인의 경우와 적록색약의 경우(빨강색과 초록색을 동일하게 처리) 2번 BFS 돌림.

#include <stdio.h>

constexpr int MAX_QUEUE_SIZE = 20000;
constexpr int MAX_COUNT = 101;

int N;

char map[MAX_COUNT][MAX_COUNT];
short group[MAX_COUNT][MAX_COUNT];
short groupForBlind[MAX_COUNT][MAX_COUNT];

int dR[] = { -1, 1, 0, 0 };
int dC[] = { 0, 0, -1, 1 };

class Point
{
public:
	int r;
	int c;

	Point() { r = c = 0; }
	Point(int r, int c) : r(r), c(c) {}
	
	bool IsInBoundary(int N)
	{
		return (r >= 0) && (r < N) && (c >= 0) && (c < N);
	}
};

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T items[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }

	void push(T item)
	{
		items[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = items[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};
Queue<Point> q;

int BFS(short (*groupMap)[MAX_COUNT], bool RGSame = false)
{
	int result = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (groupMap[i][j] == -1)
			{
				Point init(i, j);
				groupMap[i][j] = result;
				q.push(init);

				while (!q.isEmpty())
				{
					Point now = q.pop();

					for (int k = 0; k < 4; k++)
					{
						Point next(now.r + dR[k], now.c + dC[k]);
						
						if (!next.IsInBoundary(N)) continue;

						if (groupMap[next.r][next.c] == -1)
						{
							if ((map[next.r][next.c] == map[init.r][init.c]) || 
								(RGSame && ((map[init.r][init.c] == 'R' && map[next.r][next.c] == 'G') || 
									(map[init.r][init.c] == 'G' && map[next.r][next.c] == 'R'))))
							{
								groupMap[next.r][next.c] = result;
								q.push(next);
							}
						}
					}
				}

				result++;
			}
		}
	}

	return result;
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			while (true)
			{
				scanf("%c", &map[i][j]);

				if (map[i][j] != '\n') break;
			}

			group[i][j] = -1;
			groupForBlind[i][j] = -1;
		}
	}

	printf("%d\n", BFS(group));
	printf("%d\n", BFS(groupForBlind, true));
	
	return 0;
}