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

bfs 문제로 풀면 쉽게 나온다. 

map 구조

1. map 에 RGB 색상에 맞게 숫자로 저장. (그대로 해도 상관없음. 저는 보통 숫자로 합니다.)

2. 반복문을 돌면서 해당 위치가 방문되지 않았다면 bfs() 함수를 호출 한다. 

3. bfs 기본적인 알고리즘을 사용해 동일한 색상에 인접한 구간들을 다 방문 처리한다. 

4. 메인문에서 bfs 호출된 개수를 출력 ( 첫번째 답안 ) 

5. map 에서 R과 G를 동일한 번호로 저장. 

6. 2~4 번과 동일. 

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std; 
int dx[4] = { 0,0,1,-1 }; 
int dy[4] = { 1,-1,0,0 }; 
int n; 
int map[100][100];
int visited[100][100]; 
queue<pair<int, int>>q; 
void bfs() {
	while (!q.empty()) {
		int y, x; 
		tie(y, x) = q.front(); 
		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)continue; 
			if (visited[ny][nx] == 1 || map[ny][nx] != map[y][x])continue; 
			visited[ny][nx] = 1; 
			q.push({ ny,nx }); 
		}
	}
}
int main() {
	cin >> n; 
	for (int i = 0; i < n; i++) {
		string s; cin >> s; 
		for (int j = 0; j < n; j++) {
			if (s[j] == 'R')map[i][j] = 1;
			else if (s[j] == 'G')map[i][j] = 2;
			else map[i][j] = 3; 
		}
	}
	int cnt = 0; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {
				visited[i][j] = 1; 
				q.push({ i,j }); 
				bfs(); 
				cnt++; 
			}
		}
	}
	cout << cnt << " "; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 2)map[i][j] = 1; 
		}
	}
	memset(visited, 0, sizeof(visited));
	cnt = 0; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] == 0) {
				visited[i][j] = 1;
				q.push({ i,j });
				bfs();
				cnt++;
			}
		}
	}
	cout << cnt; 	
}

10026번: 적록색약