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

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

10026번: 적록색약

 

문제 분석

그림을 2차원 배열에 RGB값을 넣어서 주고, 배열 내에서 상하좌우에 같은 값이 있다면 하나의 구역으로 본다.
적록색약이 아닌 사람이 봤을 때 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 개수를 구하는 문제이다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
char picture[100][100];
bool visited[100][100];

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

void bfs(int startX, int startY, int &count, bool isRB) {
	queue<pair<int, int>> q;
	visited[startX][startY] = true;
	q.push({ startX, startY });

	while (!q.empty()) {
		pair<int, int> node = q.front();
		int nodeX = node.first;
		int nodeY = node.second;
		char nodeRGB = isRB && picture[nodeX][nodeY] == 'G'
			? 'R' : picture[nodeX][nodeY];
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextX = nodeX + dx[i];
			int nextY = nodeY + dy[i];

			if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
				char nextRGB = isRB && picture[nextX][nextY] == 'G'
					? 'R' : picture[nextX][nextY];
				if (!visited[nextX][nextY] && nodeRGB == nextRGB) {
					visited[nextX][nextY] = true;
					q.push({ nextX, nextY });
				}
			}
		}
	}
	count++;
}

void solveProblem() {
	int rgbCount = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) continue;
			bfs(i, j, rgbCount, false);
		}
	}

	for (int i = 0; i < size(visited); i++) {
		memset(visited[i], false, sizeof(visited[i]));
	}

	int rbCount = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) continue;
			bfs(i, j, rbCount, true);
		}
	}

	cout << rgbCount << " " << rbCount;
}

void getInput() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> picture[i][j];
		}
	}
}

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

	getInput();
	solveProblem();

	return 0;
}

문제 풀이

적록색약인 사람인지 판단하는 isRB 변수를 BFS 함수에 넘겨서, 적록색약인 경우에는 G를 R값으로 바꾸도록 했다.

큐를 2개를 써서 BFS 함수를 한 번만 호출하도록 구현해보려고 했지만 어차피 while문을 두 번 돌려야 하기 때문에 그냥 BFS를 2번 호출하도록 구현했다.

BFS를 두 번째 호출할 때에는 visited 배열을 초기화해야 한다는 점에 주의하자.