BaekJoon 10026 적록색약

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

소스결과 1996 KB / 0 ms

출처 Backjoon, USACO March 2014 Contest Bronze 3번

언어 C++ 17

분류 BFS DFS

 

설명

정상인이 봤을때의 그룹 수와 적록색약인 사람이 봤을 떄 그룹 수를 출력하는 문제

기존 문제와 다른점은 동일시 해야 하는 경우가 존재한다는 것

 

정상인 입장의 그룹 수는 R G B로 나누어서 그룹 수를 구하면 되지만 적록색약인 경우 R 이나 G일때 R , G를 전부 같은 색으로 판단해야 한다는 것이다.

방법은 2가지가 존재한다.

먼저 정상인 기준의 값을 전부 받은 후

R과 G를 전부 B가 아닌 특정 값으로 전부 바꾼 배열을 따로 만들어도 된다.

다른 방법은 BFS를 사용할 때 R 이나 G에 한해서 R G를 같은 그룹으로 판정 하게 하면 된다.

 

전자의 경우는 메모리를 조금 더 사용하는 경우고 후자의 경우는 연산을 추가하는 경우다

 

이 글에서 사용한 방법은 후자를 사용했다. 이유는 쓰면서 전자의 방법이 떠올랐기 때문이다.

 

알고리즘

1. RGB배열을 입력 받는다.

2. 입력 받은 배열을 BFS진행 함수에 넣는다. 매개변수로는 map의 크기와 적록색약 구분 bool 변수를 넣어준다.

3. ( 0, 0 )을 기점으로 모든 지점에 대해서 BFS를 진행한다.

 3. 1 적녹색약인 경우 현재 위치가 B가 아니라면 현재 탐색하는 노드를 Queue에 추가한다.

 3. 2 현재 위치의 색과 탐색하는 노드의 값이 일치하면 Queue에 추가한다.

4. 그룹의 수를 출력한다.

 

소스코드

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

const int MAX = 100;

char board[MAX][MAX];

short posX[4] = { 1, 0, -1, 0 };
short posY[4] = { 0, 1, 0, -1 };

struct Point {
	short x;
	short y;

	Point() {};
	Point(short x, short y) : x(x), y(y) {}
};

int func(int n, bool isRedGreen)
{
	int res = 0;
	bool visitTable[MAX][MAX];

	queue<Point> q;

	memset(visitTable, false, sizeof(visitTable));

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (visitTable[i][j])
				continue;

			q.push(Point(i, j));

			while (!q.empty())
			{
				Point cur = q.front();
				q.pop();

				if (visitTable[cur.x][cur.y])
					continue;

				visitTable[cur.x][cur.y] = true;

				for (int pos = 0; pos < 4; pos++)
				{
					short nextX = cur.x + posX[pos];
					short nextY = cur.y + posY[pos];
					if (0 <= nextX && nextX < n && 0 <= nextY && nextY < n)
					{
						if (isRedGreen && board[cur.x][cur.y] != 'B') // 적녹색약인 경우
						{
							if (board[nextX][nextY] == 'G' || board[nextX][nextY] == 'R')
								q.push(Point(nextX, nextY));
						}

						if (board[cur.x][cur.y] == board[nextX][nextY])
							q.push(Point(nextX, nextY));
					}
				}
			}
			res++;
		}

	return res;
}

int main()
{
	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> board[i];

	cout << func(n, false) << ' ' << func(n, true);

	return 0;
}