💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.

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

🔋예제 입출력

🔮예제 입력1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

🔮예제 출력1

4 3

💉문제 분석

🔋분류

그래프이론, DFS, BFS

🔋난이도

골드V

💉문제 풀이

🔋해법

정말 간단한 문제였습니다.
저는 재귀함수사용하는 dfs연습중이라서 dfs로 풀었습니다.
몇가지만 알아두시면 되겠습니다.

1. 적색맹은 빨간색, 초록색을 같다고 판단하면된다.
2. dfs는 두개로 나눠서 하시면 매우 편하실겁니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 101;

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

std::string adj[MAX];
bool visit[MAX][MAX];

void dfs1(int N, char c, int x, int y) {
	visit[y][x] = true;

	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
			if (!visit[ny][nx] && adj[ny][nx] == c) {
				visit[ny][nx] = true;
				dfs1(N, c, nx, ny);
			}
		}
	}
}

void dfs2(int N, char c, int x, int y) {
	visit[y][x] = true;

	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
			if (!visit[ny][nx]) {
				if (c != 'B') {
					if (adj[ny][nx] == 'R' || adj[ny][nx] == 'G') {
						visit[ny][nx] = true;
						dfs2(N, c, nx, ny);
					}
				}
				else {
					if (adj[ny][nx] == c) {
						visit[ny][nx] = true;
						dfs2(N, c, nx, ny);
					}
				}
			}
		}
	}
}

int main() {
	std::cin.tie(0);
	std::cout.tie(0);
	std::ios_base::sync_with_stdio(0);

	int N;

	std::cin >> N;
	for (int i = 0; i < N; ++i) std::cin >> adj[i];

	int ColorBlindness = 0;
	int Common = 0;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (!visit[i][j]) {
				dfs1(N, adj[i][j], j, i);
				++Common;
			}
		}
	}

	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) visit[i][j] = false;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (!visit[i][j]) {
				dfs2(N, adj[i][j], j, i);
				++ColorBlindness;
			}
		}
	}

	std::cout << Common << ' ' << ColorBlindness << '\n';
}

문제가 너무 쉬워서 바로 맞췄습니다.
저번에 풀던 실버dp문제가 더 어려웠던것같습니다.

확실히 백준은 문제유형에 따른 난이도배정 차이가 좀 큰듯합니다.
네트워크유량이나 강한결합요소같은거는 대부분 플래티넘이상인데 간혹가다가 실버dp문제보다 쉬운문제도 많이보이고 하니까..

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~~