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

문제

---

입출력

---

문제 요약

적록색약은 빨강(R), 초록(G)를 차이를 구분하지 못한다고 한다. 즉 적록색약이 봤을 때는 R과 G를 동일선상에 놓아야한다.

출력 값들을 보면 적록색약이 아닌 사람이 봤을 때의 구역 개수, 적록색약인 사람이 봤을 때 구역의 수를 출력해야한다.

코드 구현 순서는

 

1. 적록색약이 아닌 사람이 봤을 때의 dfs 실행

2. 적록색약의 dfs를 하기 전 G -> R 로 바꾸기

3. visited 배열 false로 다시 초기화

4. 적록색약의 dfs 실행

---

코드

#include <iostream>
#include <cstring>

using namespace std;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
char map[100][100];
bool visited[100][100];
int N;
int cnt = 0;
int no_cnt = 0;
string str;

void dfs(int x, int y) {
	visited[x][y] = true;
	char color = map[x][y];

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < N && ny < N && nx >= 0 && ny >= 0) {
			if (map[nx][ny] == color && !visited[nx][ny]) {
				dfs(nx, ny);
			}
		}
	}

}

int main() {
	cin >> N;

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

	memset(visited, false, sizeof(visited));


	//적록색약이 아닌 dfs
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				dfs(i, j);
				no_cnt++;
			}
		}
	}

	//적록색약 dfs
	// G -> R로 바꾸기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 'G') {
				map[i][j] = 'R';
			}
		}
	}

	memset(visited, false, sizeof(visited));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				dfs(i, j);
				cnt++;
			}
		}
	}

	cout << no_cnt << " " << cnt;

}