[C++] 백준 10026 : 적록색약

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

10026번: 적록색약

백준 10026번 적록색약을 풀었다.

 

DFS를 두 번 실행하면 되는 문제다.

두 번째 실행이 적록 색약인 사람이 보는 구역의 수를 구한다.

첫 번째 실행 후 visited 배열을 초기화하고, grid 배열 중 'G' 값을 'R' 값으로 바꿔줬다.

그 다음 DFS를 실행하면 문제에서 요구하는 답을 구할 수 있다.

 

아래는 전체 코드입니다.

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

int n;
int cnt1, cnt2;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
bool visited[100][100];
char grid[100][100];

void DFS(int x,int y, char c) {
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x >= 0 && next_x < n
			&& next_y >= 0 && next_y < n
			&& visited[next_x][next_y] == 0
			&& grid[next_x][next_y] == c) {
			visited[next_x][next_y] = 1;
			DFS(next_x,next_y,c);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.size(); j++)
			grid[i][j] = str[j];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {
				DFS(i, j, grid[i][j]);
				cnt1++;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visited[i][j] = 0;
			if (grid[i][j] == 'G')
				grid[i][j] = 'R';
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {
				DFS(i, j, grid[i][j]);
				cnt2++;
			}
		}
	}

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

	return 0;
}