[BOJ-10026] 적록색약

백준 10026 적록색약

 

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

10026번: 적록색약

 

 

 

문제 설명

 

 - 크기가 NxN인 그리드의 각 칸에 R, G, B 중 하나를 색칠한 그림이 있다.

 

 - 그림은 몇 개의 구역으로 나뉘어져 있고, 구역은 같은 색으로 이루어져 있다.

 

 - 같은 색상이 상, 하, 좌, 우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다.

   ( 색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다. )

 

 - 적록색인 사람은 빨간색(R)과 초록색(G)를 같은 색으로 판단한다.

 

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

---

 

입력 값

 

 - 첫째 줄에 N이 주어진다.

   ( 1 <= N <= 100 )

 

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

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 BFS를 이용하여 풀 수 있는 간단한 문제이다.

 

 - NxN의 그리드를 탐색하면서, 구역이 몇 개 있는지 구하면 되는 문제이다.

 

 - 그리드의 노드를 처음부터 탐색하면서, 이미 탐색한 구역이라면 넘어가고 탐색하지 않은 구역이라면

   해당 노드가 포함된 구역을 모두 구하면 된다.

 

 - 적록 색약인 경우 R인 노드와 G인 노드를 같은 노드로 판단하면 된다.

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

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

int N;

bool visited[101][101];

char boards[101][101];

void bfs(int y, int x, vector<char> &nowColor) {

	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int nowY = q.front().first;
		int nowX = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int nextY = nowY + dy[d];
			int nextX = nowX + dx[d];

			if (nextY < 0 || nextX < 0 || nextY >= N || nextX >= N || visited[nextY][nextX]) {
				continue;
			}

			bool nextColorSame = false;

			// 하나라도 같으면 통과
			for (char color : nowColor) {
				if (boards[nextY][nextX] == color) {
					nextColorSame = true;
					break;
				}
			}

			if (!nextColorSame) {
				continue;
			}

			visited[nextY][nextX] = true;
			q.push({ nextY,nextX });

		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	char color;
	int findOriginal=0, findRedGreen=0;

	cin >> N;


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> color;
			boards[i][j] = color;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j]) {
				continue;
			}
			vector<char> nowColor{ boards[i][j] };

			bfs(i, j, nowColor);


			findOriginal++;
		}
	}

	fill(&visited[0][0], &visited[0][0] + 101 * 101, false);

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

			vector<char> nowColor;
			if (boards[i][j] == 'B') {
				nowColor.push_back('B');
			}
			else {
				nowColor.push_back('R');
				nowColor.push_back('G');

			}

			bfs(i, j, nowColor);


			findRedGreen++;
		}
	}

	cout << findOriginal << " " << findRedGreen << "\n";



	return 0;
}