[백준 10026번 C/C++] 적록색약

 

[백준 10026번 C/C++] 적록색약

 

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

10026번: 적록색약

---

 

 

해결전략

 

너비우선탐색 BFS

---

 

 

코드

 

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

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int n;
vector<vector<char>> v; // 각 칸의 색을 기록
vector<pair<int, int>> R, G, B; // R, G, B의 위치를 기록

// BFS 함수를 통해 특정 색상의 영역 개수를 세는 함수
int BFS(const vector<pair<int, int>>& color, const char& colorType1, const char& colorType2)
{
	int cnt = 0; // 영역의 개수를 저장하는 변수
	queue<pair<int, int>> Q;
	vector<vector<int>> ch(n, vector<int>(n, 0)); // 방문 여부를 체크하는 2차원 벡터

	for (int i = 0; i < color.size(); i++)
	{
		if (ch[color[i].first][color[i].second] == 0) // 해당 좌표를 방문한적이 없으면
		{
			Q.push({ color[i].first, color[i].second }); // 큐에 넣음
			ch[color[i].first][color[i].second] = 1; // 방문 표시

			while (!Q.empty())
			{
				int y = Q.front().first;
				int x = Q.front().second;
				Q.pop();

				for (int i = 0; i < 4; i++)
				{
					int ny = y + dirY[i];
					int nx = x + dirX[i];

					if (ny < 0 || n <= ny || nx < 0 || n <= nx) continue;

					// 아직 방문하지 않았고, 같은 색상이라면 큐에 넣고 방문 표시
					if (ch[ny][nx] == 0 && (v[ny][nx] == colorType1 || v[ny][nx] == colorType2)) 
					{
						Q.push({ ny, nx });
						ch[ny][nx] = 1;
					}
				}
			}
			cnt++; // 영역 개수 증가
		}
	}

	return cnt; // 영역의 개수 반환
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n, vector<char>(n));
	string input;
	for (int y = 0; y < n; y++) {
		cin >> input;

		for (int x = 0; x < n; x++) {
			v[y][x] = input[x];
			// R, G, B의 좌표를 각각 기록
			if (v[y][x] == 'R') R.push_back({ y, x });
			else if (v[y][x] == 'G') G.push_back({ y, x });
			else if (v[y][x] == 'B') B.push_back({ y, x });
		}
	}

	int answer1 = BFS(R, 'R', 'R') + BFS(G, 'G', 'G') + BFS(B, 'B', 'B');

	// 적록색약. R과 G를 하나로 합침
	for (int i = 0; i < G.size(); i++) {
		R.push_back({ G[i].first, G[i].second });
	}
	int answer2 = BFS(R, 'R', 'G') + BFS(B, 'B', 'B');

	cout << answer1 << " " << answer2 << "\n";

	return 0;
}

 

---