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

문제링크:https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

dfs문제입니다. bfs로도 풀 수 있고 단순히 완전탐색을 하면서 갯수를 세어주면 되는 간단한 문제였습니다. 

방문했는지 여부와 같은색인지를 판별해서 탐색을 했습니다. bfs, dfs 모두 쉽게 구현가능하니까 직접 구현해보시면 좋을 것 같습니다.

 

 

너무쉬워서 설명은 생략하겠습니다. 

 

 

정답코드입니다. 화이팅 :)

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int n = 0,normal =0,medicine=0;
string arr[100];
bool visited[101][101] = { 0 };
int dex[4] = { 1,-1,0,0 };
int dey[4] = { 0, 0,1,-1 };
void dfs(char color,int x,int y) {

	visited[y][x] = 1;
	
	for (int i = 0; i < 4; i++) {
		int yy = y + dey[i];
		int xx = x + dex[i];
		if (xx >= 0 && xx < n && yy >= 0 && yy< n)
			if (!visited[yy][xx] && arr[yy][xx] == color)
				dfs(color, xx, yy);
	}
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for(int i=0;i<n;i++)
		for (int j = 0; j < arr[i].size(); j++) 
			if (!visited[i][j]) {
				dfs(arr[i][j], j, i);
				normal++;
			}

	memset(visited, 0, sizeof(visited));

	for (int i = 0; i<n; i++)
		for (int j = 0; j < arr[i].size(); j++) 
			if (arr[i][j] == 'R') arr[i][j] = 'G';

	for (int i = 0; i<n; i++)
		for (int j = 0; j < arr[i].size(); j++)
			if (!visited[i][j]) {
				dfs(arr[i][j], j, i);
				medicine++;
			}

	cout << normal << ' '<< medicine << endl;
	
}