[백준][DFS] 적록색약

백준 알고리즘

DFS

C++

 

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

10026번: 적록색약

 

#include <iostream>
#include <algorithm>
using namespace std;

int T;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
char map[101][101];
int visited[100][100] = { 0, };
int visited_rg[100][100] = { 0, };

void dfs(int x, int y, char c);
void dfs_rg(int x, int y, char c);

int main() {
	int count = 0, count_rg = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> map[i];
	}

	for (int i = 0; i < T; i++) {
		for (int j = 0; j < T; j++) {
			if (visited[i][j] == 0) {
				count++;

				dfs(i, j, map[i][j]);
			}
		}
	}

	for (int i = 0; i < T; i++) {
		for (int j = 0; j < T; j++) {
			if (visited_rg[i][j] == 0) {
				count_rg++;

				dfs_rg(i, j, map[i][j]);
			}
		}
	}

	cout << count << ' ' << count_rg;

	return 0;
}

void dfs(int x, int y, char c) {
	visited[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (0 <= nx && nx < T && 0 <= ny && ny < T) {
			if (map[nx][ny] == c && visited[nx][ny] == 0) {
				dfs(nx, ny, c);
			}
		}
	}
}

void dfs_rg(int x, int y, char c) {
	visited_rg[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (0 <= nx && nx < T && 0 <= ny && ny < T) {
			if (visited_rg[nx][ny] == 0) {
				if (c == 'B' && map[nx][ny] == c) {
					dfs_rg(nx, ny, c);
				}
				if (c != 'B' && (map[nx][ny] == 'R' || map[nx][ny] == 'G')) {
					dfs_rg(nx, ny, c);
				}
			}
		}
	}
}