[백준] 10026번 적록색약 (C++)

문제

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

 

n * n 크기의 R, G, B로이루어진 그림의 구역 수를 구하는 문제이다.

 

이때, 적록색약 유무에 따른 그림 영역의 갯수를 출력하면 된다.

 

적록 색약이 있는 사람은 R, G의 구분을 못한다.

ex) 적록 색약 X ▶ R (1), G(1), B(1) = 3개,  적록 색약 O ▶ RG(1), B(1) = 2개

풀이

일반적인 그림이 담겨있는 2차원 벡터와 적록색약을 가진 사람이 보는 그림이 담긴 2차원 벡터 2개를 만들고,  이를 BFS를 이용하여 탐색했다. 

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n ;

void BFS(pair<int, int> startPoint,vector<vector<int>> &arr,bool visited[101][101])
{
	queue<pair<int, int> > q;
	q.push(startPoint);
	visited[startPoint.first][startPoint.second] = true;

	int target = arr[startPoint.first][startPoint.second], count = 1;
	while(!q.empty())
	{
		pair<int, int> p = q.front();
		q.pop();

		for(int i = 0; i < 4; i++)
		{
			int moveY = p.first + dy[i];
			int moveX = p.second + dx[i];

			if(moveY < 0 || moveX < 0 || moveY >= n || moveX >= n)
				continue;

			if(!visited[moveY][moveX] && arr[moveY][moveX] == target)
			{
				q.push({moveY, moveX});
				visited[moveY][moveX] = true;
			}
		}
	}
}

void Search(vector<vector<int>> &arr)
{
	bool visited[101][101] = {false, };
	int count = 0 ;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(!visited[i][j])
			{
				BFS({i,j}, arr,visited);
				count++;
			}
		}
	}
	cout << count << " ";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	vector<vector<int> > arr01(n, vector<int>(n));
	vector<vector<int> > arr02(n, vector<int>(n));
	for(int i = 0; i < n; i++)
	{
		string input;
		cin >> input;
		for(int j = 0; j < input.length(); j++)
		{
			if(input[j] == 'R')
			{
				arr01[i][j] = arr02[i][j] = 1;
			}
			else if(input[j] == 'G')
			{
				arr02[i][j] = 1;
				arr01[i][j] = 2;
			}
			else
			{
				arr01[i][j] = arr02[i][j] = 3;
			}
		}
	}

	Search(arr01);
	Search(arr02);
	return 0;
}