[백준/BOJ] 10026번 적록색약 (C++)

www.acmicpc.net/problem/10026

10026번: 적록색약

난이도가 쉬운 BFS 문제였습니다.

적록색약이 아닌 사람이 봤을 때 구역의 총 개수를 먼저 구한 후, 색의 입력을 받은 map 배열에서 G의 값을 전부 R로 바꾸어 적록색약인 사람이 봤을 때 구역의 총 개수를 구하면 되는 문제입니다.

 

#include <iostream>
#include <deque>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int n, first, second;
char map[101][101];
bool visit[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(int sx, int sy) {
	queue<pair<int, int> > q;
	q.push({ sx, sy });
	visit[sx][sy] = true;
	char pivot = map[sx][sy];
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visit[nx][ny] && map[nx][ny] == pivot) {
				q.push({ nx, ny });
				visit[nx][ny] = true;
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for(int j = 0; j < str.size(); j++) {
			map[i][j] = str[j];
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(!visit[i][j]) {
				BFS(i, j);
				first++;
			}
		}
	}
	
	memset(visit, false, sizeof(visit));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(map[i][j] == 'G') map[i][j] = 'R';
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(!visit[i][j]) {
				BFS(i, j);
				second++;
			}
		}
	}
	
	cout << first << " " << second;
}