백준 10026번 적록색약(c++)

10026번: 적록색약

문제 분석

문제 조건

문제는 적록색약인 사람이 본 그림의 구역과, 적록색약이 아닌 사람이 본 그림의 구역을 출력하도록 한다.

2차원 배열의 그림판이 주어지고, 그림판의 각 칸은 R, G, B 중 하나가 칠해져있다.

적록색약인 사람은 R와 G의 색을 구분하지 못하기에 같은 구역으로 처리한다.

이때, 상하좌우로 인접한 경우에는 같은 구역이라 한다.

 

 

💡 문제를 마주하자마자, 깊이 우선 탐색(DFS)로 풀어야한다는 것을 알아야 한다.

깊이 우선 탐색의 대표적인, 인접한 구역을 찾아 표시하는 문제이기 때문이다.

 

 

🤔: DFS까지는 알겠어! 그렇다면 적록색약인 사람과 아닌 사람을 어떻게 구분할까..? 또, 적록색약인 사람에 대한 조건식을 어떻게 구현할까?

---

문제 풀이

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

문제의 예를 가지고 함께 설명하겠다.

 

먼저 모든 칸을 탐색하면서, 칸의 구역을 확인할 것이다. 

이 때, [0][0]과 [0][1]은 같은 구역인 것처럼, 같은 구역의 경우를 구분해주어야한다.

💡방문한 칸인지 확인하기 위해서, 동일한 크기의 배열(bool 형)을 만들어 구역이 정해진 칸은 true 표시를 하여 방문했음을 확인한다. 

만약 true 표시된 칸에 방문한다면, 이미 구역이 정해졌기에 탐색할 필요가 없다!
적록색약인 사람의 배열, 아닌 사람의 배열 총 2개의 배열을 만들어준다.

 

 

 

이제는 적록색약인 사람일 때, R G B의 구분을 위한 조건문을 작성해야 한다.

 

'R'이나 'G'를 시작으로

if) 마주한 색이 'R'이나 'G'일 경우

-> 같은 구역이다!

 

if) 마주한 색이 'B'일 경우

-> 다른 구역이다!

 

✅즉, R, G를 시작으로 B만 아니면 같은 구역으로 생각한다.

 

 

C++ 풀이

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N;
int cnt1 = 0, cnt2 = 0; 
// cnt1 : 적록색약이 아닌 사람이 본 구역, cnt2 : 적록색약인 사람이 본 구역

vector<string> draw; // 전체 구역
vector<vector<bool>> visited1; // 적록색약이 아닌 사람
vector<vector<bool>> visited2; // 적록색약인 사람

void normalColor(int row, int col, int now, char ch) { // 적록색약이 아닌 사람
	// base case
	if (row < 0 || col < 0 || row == N || col == N || visited1[row][col] || draw[row][col] != ch)
		return;
    // ch : 현재 색상
    // ch와 draw[row][col]이 다를 경우 함수를 탈출함.
    

	// general case
	visited1[row][col] = true; 
	if (now == 0)
		cnt1++;
	now++;
	
    // 상하좌우 확인
	normalColor(row + 1, col, now, ch);
	normalColor(row, col + 1, now, ch);
	normalColor(row - 1, col, now, ch);
	normalColor(row, col - 1, now, ch);

}

void Color(int row, int col, int now, char ch) { // 적록색약인 사람
	// base case
	if (row < 0 || col < 0 || row == N || col == N || visited2[row][col])
		return;

	if (ch == 'B') { // Blue일 경우에는 적록색약이 아닌 사람과 동일한 조건임.
		if (draw[row][col] != ch)
			return;
	}
	else { // Red나 Green일 경우, Blue일 때만 함수 탈출함.
		if (draw[row][col] == 'B')
			return;
	}

	//general case
	visited2[row][col] = true;
	if (now == 0)
		cnt2++;
	now++;

    // 상하좌우 확인
	Color(row + 1, col, now, ch);
	Color(row, col + 1, now, ch);
	Color(row - 1, col, now, ch);
	Color(row, col - 1, now, ch);
}

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

	cin >> N;

	draw.resize(N, "");
	visited1.resize(N, vector<bool>(N, false));
	visited2.resize(N, vector<bool>(N, false));


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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int now1 = 0, now2 = 0;
			normalColor(i, j, now1, draw[i][j]);

			Color(i, j, now2, draw[i][j]);

		}
	}

	cout << cnt1 << ' ' << cnt2;

	return 0;
}

코드 리뷰는 언제나 환영입니다!