백준 10026 c++ "적록색약" -[PlusUltraCode]

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

10026번: 적록색약

[필자 사고]

 

이 문제는 전형적인 2차원 배열 BFS탐색문제이다.

 

 BFS탐색을 적록색약인 사람과 아닌 사람 구별해서 해주면 문제를 쉽게 풀 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

vector<vector<int>> Arr;
vector<vector<int>> Arr2;
vector<vector<bool>> visited;
int N;

typedef pair<int, int> Node;
//R==1 G==2 B==3

void Input() {
	cin >> N;
	Arr.resize(N );
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
		visited[i].resize(N, false);
	}
	Arr2 = Arr;
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			if (str[k] == 'G') {
				Arr2[i][k] = 1;
				Arr[i][k] = 2;
			}
			else if (str[k] == 'R') {
				Arr2[i][k] = 1;
				Arr[i][k] = 1;
			}
			else {
				Arr2[i][k] = 3;
				Arr[i][k] = 3;
			}
		}
	}
}
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}


void BFS(int sero,int garo,int nowNumber) {
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = true;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				Arr[nextSero][nextGaro] == nowNumber &&
				visited[nextSero][nextGaro] == false){
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
			}
		}
	}
}
void Solve() {
	int RGB_Person = 0;
	int RB_Person = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (visited[i][k] == false) {
				RGB_Person++;
				BFS(i, k, Arr[i][k]);

			}
		}
	}
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N,false);
	}
	Arr = Arr2;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (visited[i][k] == false) {
				RB_Person++;
				BFS(i, k, Arr[i][k]);

			}
		}
	}
	cout << RGB_Person << " " << RB_Person;
}


int main(void) {
	Input();
	Solve();

}