BOJ 10026 : 적록색약

BOJ 10026

 

 

[BOJ 10025(G5) 리뷰]

 

RGB색상이 주어지는데 적록색약은 빨간색과 초록색을 구분하지 못한다고 한다.

각각의 색깔이 구분되는 구역의 수를 세야한다.

정상인은 세가지 색에 대해 구분을 할 수 있지만 적록색약은 빨간색과 초록색을 한가지 색으로 구분하게 된다. 

이 때 정상인이 바라보는 구역과 적록색약이 바라보는 구역의 수를 각각 출력하면된다.

 

한번의 연산만으로 수행할 수 있을까싶어 머리를 굴려봤지만 아이디어가 떠오르지 않았다.

그래서 그냥 BFS를 정상인의 경우와 적록색약의 경우로 나누어 탐색하여 결과값을 출력했다.

1<=N<=100이기에 시간초과는 나지 않았다.

 

*시행착오

첨에 check를 string으로 선언했는데 string으로 선언할 경우 fill을 이용한 초기화가 안된다.

또한 초기화가 안된 index에 접근이 불가능하다.

ex. string a[101];

cout<<a[0][1] <-- 이러한 접근이 불가능하다. 문자열 입력이 들어와야 그때 접근이 가능하다.

첨엔 몰랐는데 디버깅하면서 발견했고 char[][]배열을 통해 해결했다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second
string board[101];
char check[101][101]; 
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1,  0, -1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> board[i];

	for (int i=0;i<n;i++)
		fill(check[i], check[i] + n, '0');

	//case 1
	int case1 = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[i][j] != '0') continue;
			case1++;
			queue <pair<int, int>> Q;
			char color = board[i][j];
			check[i][j] = color;
			Q.push({ i,j });
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if (check[nx][ny] != '0' || board[nx][ny] != color) continue;
					check[nx][ny] = color;
					Q.push({ nx,ny });
				}
			}
		}
	}

	cout << case1<<' ';

	//case 2

	for (int i = 0; i < n; i++)
		fill(check[i], check[i] + n, '0');

	int case2 = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[i][j] != '0') continue;
			case2++;
			queue <pair<int, int>> Q;
			char color = board[i][j];
			check[i][j] = color;
			Q.push({ i,j });
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if (color == 'R' || color == 'G')
					{
						if (check[nx][ny] != '0' || board[nx][ny]=='B') continue;
						check[nx][ny] = color;
						Q.push({ nx,ny });
					}
					else
					{
						if (check[nx][ny] != '0' || board[nx][ny] != color) continue;
						check[nx][ny] = color;
						Q.push({ nx,ny });
					}
				}
			}
		}
	}
	cout << case2;

}