10026번: 적록색약

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

10026번: 적록색약

1. 문제 분석

구역의 개수를 세는 그래프 문제이다.

적록색맹과 아닌사람을 각각 출력하는 문제인데 그리드와 체크를 따로 만들어 주어서 해결했다.

2. 코드 분석

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

char grid[100][100];
char grid_RG[100][100];
bool check[100][100];
bool check_RG[100][100];
queue<pair<int, int>> q;

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

int N;
void bfs()
{
	while (q.empty() != 1)
	{
		int size = q.size();
		for (int i = 0;i < size;i++)
		{
			int y = q.front().first;
			int x = q.front().second;
			char first = grid[y][x];
			q.pop();
			for (int i = 0;i < 4;i++)
			{
				int move_y = y + dy[i];
				int move_x = x + dx[i];
				if (move_y >= 0 && move_y < N && move_x >= 0 && move_x < N)
				{
					if (grid[move_y][move_x] == first && check[move_y][move_x] == false)
					{
						check[move_y][move_x] = true;
						q.push({ move_y,move_x });
					}
				}
			}
		}
	}
}
void bfs_RG()
{
	while (q.empty() != 1)
	{
		int size = q.size();
		for (int i = 0;i < size;i++)
		{
			int y = q.front().first;
			int x = q.front().second;
			char first = grid_RG[y][x];
			q.pop();
			for (int i = 0;i < 4;i++)
			{
				int move_y = y + dy[i];
				int move_x = x + dx[i];
				if (move_y >= 0 && move_y < N && move_x >= 0 && move_x < N)
				{
					if (grid_RG[move_y][move_x] == first && check_RG[move_y][move_x] == false)
					{
						check_RG[move_y][move_x] = true;
						q.push({ move_y,move_x });
					}
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	char c;
	cin >> N;
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			cin >> c;
			grid[i][j] = c;
			if (c == 'G') grid_RG[i][j] = 'R';
			else grid_RG[i][j] = c;
		}
	}
	int cnt = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			if (check[i][j] == false) {
				check[i][j] = true;
				q.push({ i,j });
				bfs();
				cnt++;
			}
		}
	}
	cout << cnt << " ";
	cnt = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < N;j++)
		{
			if (check_RG[i][j] == false) {
				check_RG[i][j] = true;
				q.push({ i,j });
				bfs_RG();
				cnt++;
			}
		}
	}

	cout << cnt;
	return 0;
}

3. 키워드

#BFS