백준 10026: 적록색약

문제 요약

2차원 배열로 색칠된 그림이 주어지면, 적록색약이 아닌 사람이 보았을 때의 구역의 수와 적록색약인 사람이 보았을 때의 구역의 수를 출력한다.
적록색약인 사람은 인접한 빨간색과 초록색에 대해 색상의 차이를 느끼지 못한다.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• BFS

문제 풀이

사실 문제를 보고 얼마 지나지 않아 해결방법은 바로 떠올랐다.

BFS와 DFS를 동시에 활용하는 방법인데, 일반적인 사람의 BFS와 DFS, 적록색약인 사람의 BFS와 DFS를 따로 돌려야된다는 것이다.

적록 색약의 경우 현재 탐색중인 노드가 G라고 하면, 다음 노드가 R일 때에도 똑같이 탐색해야 할 것이다. 반대의 경우도 마찬가지.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>

using namespace std;

string ary[100];
bool visited[101][101] = { false };
int n, res1 = 0, res2 = 0;
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
queue<pair<int, int>> q;

void dfs(int y, int x)
{
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dir[i][0];
		int nx = x + dir[i][1];
		if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
			if (!visited[ny][nx]) {
				if (ary[y][x] == ary[ny][nx])
					dfs(ny, nx);
				else
					q.push({ ny, nx });
			}			
		}
	}
}
void dfs2(int y, int x)	// 색약 dfs
{
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int ny = y + dir[i][0];
		int nx = x + dir[i][1];
		if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
			if (!visited[ny][nx]) {
				if ((ary[y][x] == ary[ny][nx]) || (ary[y][x] == 'G' && ary[ny][nx] == 'R') || (ary[y][x] == 'R' && ary[ny][nx] == 'G'))
					dfs2(ny, nx);
				else
					q.push({ ny, nx });
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> ary[i];
	q.push({ 0,0 });
	while (!q.empty()) {
		auto stt = q.front();
		q.pop();
		if (visited[stt.first][stt.second]) continue;
		dfs(stt.first, stt.second);
		res1++;
	}
	memset(visited, false, sizeof(visited));
	q.push({ 0,0 });

	while (!q.empty()) {
		auto stt = q.front();
		q.pop();
		if (visited[stt.first][stt.second]) continue;
		dfs2(stt.first, stt.second);
		res2++;
	}
	printf("%d %d", res1, res2);
	return 0;
}