BaekJoon 10026번: 적록색약(C++)

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

10026번: 적록색약

풀이법

1) BFS를 활용하여 몇 개의 덩어리가 존재하는지 묻는 문제이다.

2) visit 배열을 두어 한 번 방문한 곳은 다시 방문 안하는 것을 활용하면 더 쉽게 풀 수 있다.

3) 총 두번이 반복 되어야 하니 visit 배열은 초기화 시켜야 한다.

4) 두 번째에 적록 색약이신 분들을 위해 R과G 가 인접한 부분은 G->R로 바꾸는 방식으로 문제를 해결했다

(for문을 활용하는 것 보다는 queue를 활용하여 R에서 G로 바꾸는 것이 편할 것이다.)

for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 1)
				q.push({ i,j });
		}
	}
	while (!q.empty())
	{
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int bx = tx + vx[i];
			int by = ty + vy[i];
			if (bx < 0 || by < 0 || bx >= n || by >= n)
				continue;
			if (arr[bx][by] == 2)
			{
				arr[bx][by] = 1;
				q.push({ bx,by});
			}
		}
	}

실제 queue에 R(1로 매핑)인 값들을 모두 넣어 두고, 근방에 G(2로 매핑)가 있는 경우 이를 R로 바꾸어 주었다.

G->R로 바뀌었을 때, 또 인근 값에 G가 있는지 확인하는 과정은 for문 보다는 queue를 활용하는 것이 더 낫다고 판단하여 해당 방식을 활용했다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
using namespace std;

int n;
int arr[101][101];
bool visited[101][101];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int cnt = 0;
void bfs(int e,int w)
{
	queue<pair<int,pair<int, int>>> q;
	visited[e][w] = true;
	q.push({ e,{w,arr[e][w]} });
	cnt++;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int color = q.front().second.second;
		q.pop();
		bool chk = false;
		for (int i = 0; i < 4; i++)
		{
			int bx = nowX + vx[i];
			int by = nowY + vy[i];
			if (bx < 0 || by < 0 || bx >= n || by >= n)
				continue;
			if (arr[bx][by] == color && !visited[bx][by])
			{
				chk = true;
				visited[bx][by] = true;
				q.push({ bx,{by,color} });
			}
		}
	}
}
void rgb()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			visited[i][j] = false;
		}
	}
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 1)
				q.push({ i,j });
		}
	}
	while (!q.empty())
	{
		int tx = q.front().first;
		int ty = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int bx = tx + vx[i];
			int by = ty + vy[i];
			if (bx < 0 || by < 0 || bx >= n || by >= n)
				continue;
			if (arr[bx][by] == 2)
			{
				arr[bx][by] = 1;
				q.push({ bx,by});
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
		{
			if (s[j] == 'R')
				arr[i][j] = 1;
			else if (s[j] == 'G')
				arr[i][j] = 2;
			else
				arr[i][j] = 3;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j])
				bfs(i,j);
		}
	}
	cout << cnt<<" ";
	cnt = 0;
	rgb();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j])
				bfs(i, j);
		}
	}
	cout << cnt;
}