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

문제

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

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

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

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

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

입력

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

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

출력

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

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

풀이

색칠하는 개념을 떠올려보았다,
R -> G -> B순으로한다면
R에해당하는 아무 좌표하나를 찾아서 BFS로 같은 R만 모두 칠한다.
그리고 남은 R이있다면 반복하여
반복한 횟수를 체크.
G, B도 마찬가지고,
적록색약도 구해야하므로 R 과 G를 같은색으로 보고도 반복해본다.

1. 프로그램의 메인부분
   
2. 색을 칠하는 부분
   
3. 색을 칠하기전에, 색의 위치를 찾는 부분
   위치를 pair<int, int>로 리턴한다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::pair; using std::queue;
typedef pair<int, int> pii;
int n, R=0, G=0, B=0, RG=0;
char** picture, **check;
bool** visited;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pii> loc;

void func();
void init();
void clear();
bool checkColor(char c1, char c2, char**& check);
pii findColor(char c1, char c2, char**& check);
void pastePicture();

void func() {
	pastePicture();
	while (checkColor('R', 'R', check)) R++;
	while (checkColor('G', 'G', check)) G++;
	while (checkColor('B', 'B', check)) B++;
	pastePicture();
	while (checkColor('R', 'G', check)) RG++;
	printf("%d %d", R + G + B, RG + B);
}

void clear() {
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) visited[i][j] = false;
}

void pastePicture() {
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) check[i][j] = picture[i][j];
}

//해당 색상을 하나 찾아서 BFS를 진행하여 같은 색상만 지워간다.
//만약 해당 색상이 남아있지않으면 false 리턴
bool checkColor(char c1, char c2, char**&check) {
	clear();
	pii p = findColor(c1, c2, check);
	int start_x = p.first;
	int start_y = p.second;
	if (start_x == -1 && start_y == -1) return false;
	loc.push({ start_x, start_y });
	check[start_x][start_y] = 'X';
	visited[start_x][start_y] = true;

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

		for (int dir = 0; dir < 4; dir++) {
			int xx = x + dx[dir];
			int yy = y + dy[dir];

			if (xx < 0 || yy < 0 || xx == n || yy == n) continue; //올바르지않은범위이면 제외
			if (check[xx][yy] != c1 && check[xx][yy] != c2) continue; //다른색이면 제외
			if (!visited[xx][yy]) {
				visited[xx][yy] = true;
				check[xx][yy] = 'X'; //찾았음을 체크

				loc.push({ xx, yy });
			}
		}
	}
	return true;
}

pii findColor(char c1, char c2, char**&check) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (check[i][j] == c1 || check[i][j] == c2)
				return { i, j };
	return { -1, -1 };
}

void init() {
	scanf("%d", &n);
	picture = new char* [n];
	visited = new bool* [n];
	check = new char* [n];
	for (int i = 0; i < n; i++) {
		picture[i] = new char[n];
		visited[i] = new bool[n] ;
		check[i] = new char[n];
		char _;
		scanf("%c", &_);
		for (int j = 0; j < n; j++) {
			scanf("%c", &picture[i][j]);
		}
	}
}

int main() {
	init();
	func();

	return 0;
}