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

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

 

코드

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int N;
char grid[101][101];		// R/G/B
int normal[101][101];		// 적록색약이 아닌 사람
int blindness[101][101];	// 적록색약인 사람

// normal grouping
void bfs1(int r, int c, int cnt)
{
	queue< pair<int, int> > q;
	pair<int, int> curr, next;
	int d[] = {-1, 1, 0, 0};
	int i;

	normal[r][c] = cnt;
	q.push(make_pair(r, c));
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 상하죄우에 대하여
		for (i = 0; i < 4; i++)
		{
			next = make_pair(curr.first + d[i], curr.second + d[3 - i]);
			// 범위를 벗어나면 패스
			if (next.first < 0 || next.first >= N || next.second < 0 || next.second >= N)
				continue;
			// 이미 다른 그룹에 속해 있다면 패스
			if (normal[next.first][next.second] != 0)
				continue;
			// 같은 색이 아니면 패스
			if (grid[next.first][next.second] != grid[r][c])
				continue;
			// 그룹 번호를 저장하고 큐에 삽입
			normal[next.first][next.second] = cnt;
			q.push(next);
		}
	}
}

// blindness grouping
void bfs2(int r, int c, int cnt)
{
	queue< pair<int, int> > q;
	pair<int, int> curr, next;
	int d[] = {-1, 1, 0, 0};
	int i;
	bool is_blue;

	if (grid[r][c] == 'B')	// B
		is_blue = true;
	else			// R/G -> 하나의 색으로 취급
		is_blue = false;
	
	blindness[r][c] = cnt;
	q.push(make_pair(r, c));
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 상하좌우에 대하여
		for (i = 0; i < 4; i++)
		{
			next = make_pair(curr.first + d[i], curr.second + d[3 - i]);
			// 범위를 벗어나면 패스
			if (next.first < 0 || next.first >= N || next.second < 0 || next.second >= N)
				continue;
			// 이미 다른 그룹에 속해 있다면 패스
			if (blindness[next.first][next.second] != 0)
				continue;
			// 같은 색이 아니면 패스
			if (is_blue && grid[next.first][next.second] != 'B')
				continue;
			if (!is_blue && grid[next.first][next.second] == 'B')
				continue;
			// 그룹 번호를 저장하고 큐에 삽입
			blindness[next.first][next.second] = cnt;
			q.push(next);
		}
	}
}

int main()
{
	int i, j;
	int cnt1 = 0;
	int cnt2 = 0;
	string s;

	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> s;
		for (j = 0; j < N; j++)
		{
			grid[i][j] = s[j];
		}
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			// 아직 그룹이 정해지지 않은 좌표에 대하여 grouping
			if (normal[i][j] == 0)
				bfs1(i, j, ++cnt1);
			if (blindness[i][j] == 0)
				bfs2(i, j, ++cnt2);
		}
	}
	cout << cnt1 << " " << cnt2 << endl;
	return 0;
}

 

링크

10026번: 적록색약

inbdni/Baekjoon