(c++)백준 10026번: 적록색약

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

10026번: 적록색약

[풀이]

1. bfs를 사용하여 구역의 수를 구하였다.

2. 적록색약이 아닌 사람의 경우와 적록색약인 사람의 경우를 따로 함수로 구현했다.

3. bfs를 부르는 수 == 구역의 수

 

#include <iostream>
#include <queue>
#include <string>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
};

int N;
int Map[100][100];
bool visited[100][100];
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

//적록색약이 아닌 사람들
void RGB(int startx, int starty) {
	queue<Pos>q;
	q.push({ startx,starty });
	visited[startx][starty] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] == true)
				continue;
			//현재 칸과 다음 칸의 색이 같을때
			if (Map[nx][ny] == Map[x][y]) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

//적록색약인 사람들
void R_B(int startx, int starty) {
	queue<Pos>q;
	q.push({ startx,starty });
	visited[startx][starty] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny] == true)
				continue;
			//현재 칸과 다음 칸의 색이 같을때, 둘 중 하나가 R이고 다른 하나가 G일 때
			if (Map[nx][ny] == Map[x][y] || (Map[nx][ny] == 'R' && Map[x][y] == 'G') || (Map[nx][ny] == 'G' && Map[x][y] == 'R')) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}
}

void solution() {
	cin >> N;
	string s;
	int rgb = 0;//적록색약이 아닌 사람이 보는 구역의 수
	int r_b = 0;//적록색약인 사람이 보는 구역의 수
	for (int i = 0; i < N; i++) {
		cin >> s;
		for (int j = 0; j < N; j++) {
			Map[i][j] = s[j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == false) {
				RGB(i, j);
				rgb++;
			}
		}
	}
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == false) {
				R_B(i, j);
				r_b++;
			}
		}
	}
	cout << rgb << ' ' << r_b << '\n';
}

int main() {
	solution();
	return 0;
}