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

#include <iostream>
#include <queue>

using namespace std;

queue<pair<int,int> > Q;

int arr[101][101];

int visited[101][101];

void BFS(int val);

int a=0;

int main(void)
{

	cin>>a;
	
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<a; j++)
		{
			char k;
			cin>>k;
			if(k=='R')
			{
				arr[i][j]=0;
			}
			else if(k=='G')
			{
				arr[i][j]=1;
			}
			else
			{
				arr[i][j]=2;
			}
		}
	}
	
	int count=0;
	
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<a; j++)
		{
			if(visited[i][j]==0)
			{
				Q.push(make_pair(i,j));
				visited[i][j]=1;
				BFS(arr[i][j]);
				count++;
			}	
		}
	}
	
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<a; j++)
		{
			visited[i][j]=0;
			if(arr[i][j]==1)
			{
				arr[i][j]=0;
			}
		}
	}
	
	int count2=0;
	
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<a; j++)
		{
			if(visited[i][j]==0)
			{
				Q.push(make_pair(i,j));
				visited[i][j]=1;
				BFS(arr[i][j]);
				count2++;
			}	
		}
	}
	
	cout<<count<<" "<<count2;
	
	return 0;
}

void BFS(int val)
{
	while(!Q.empty())
	{
		int i=Q.front().first;
		int j=Q.front().second;
		Q.pop();
		
		if(arr[i+1][j]==val&&visited[i+1][j]==0&&i+1<a)
		{
			visited[i+1][j]=1;
			Q.push(make_pair(i+1,j));
		}
		if(arr[i-1][j]==val&&visited[i-1][j]==0&&i-1>-1)
		{
			visited[i-1][j]=1;
			Q.push(make_pair(i-1,j));
		}
		if(arr[i][j+1]==val&&visited[i][j+1]==0&&j+1<a)
		{
			visited[i][j+1]=1;
			Q.push(make_pair(i,j+1));
		}
		if(arr[i][j-1]==val&&visited[i][j-1]==0&&j-1>-1)
		{
			visited[i][j-1]=1;
			Q.push(make_pair(i,j-1));
		}
	}
}

음 나는 문자열이 싫어서 숫자로 다 바꿔버리고 시작했다.

R=0, G=1, B=2

 

이 문제를 BFS로 접근해서 풀었는데 다 풀고 나니까 BFS보다 DFS를 사용해서 푸는 것이 좋아 보인다.

그냥 깊이 우선 탐색을 통해 접근하면 visited만 가지고 해결할 문제를 굳이 BFS를 사용해서 Queue의 공간을 더 사용한게 아닌가 싶다.

 

1.2차원 배열 행과 열을 모두 확인한다.

2.만약 visited가 0이면 BFS로 탐색한다.

3.이웃 노드의 값이 같으면 확장, 다르면 멈춘다.

 

일단 적록색맹이 아닌 사람의 구역수를 먼저 구하고 

for(int i=0; i<a; i++)
	{
		for(int j=0; j<a; j++)
		{
			visited[i][j]=0;
			if(arr[i][j]==1)
			{
				arr[i][j]=0;
			}
		}
	}

적록색맹인 사람의 구역 수는 visited를 초기화 시켜주고 arr[i][j]가 1이면 모두 0으로 바꿔준 뒤 다시 BFS로 탐색하였다.