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

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

---

문제 설명

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

---

입력 설명

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

---

출력 설명

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

---

예제 입력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

---

예제 출력

4 3

---

아이디어

적록색약인 사람과 아닌 사람의 배열을 따로 만들어서 각각 BFS를 돌린 후 출력한다.

---

알고리즘

적록색약인 사람은 R과 G를 구별할 수 없기 때문에 입력에 R이 들어오면 배열에 R로 기록하고 입력에 G가 들어와도 배열에는 R로 기록한다. 적록색약이 아닌 사람은 R, G, B를 구별해서 기록한다.

이후 적록색약인 사람과 아닌 사람의 배열에서 i=1, j =1에서부터 i=N, j=N까지 vec[i][j]에 'X'이외의 R이나 G나 B가 들어있다면 해당 칸에서부터 BFS를 실행한다. 이후 결과를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(vector<vector<char>> &vec, int a, int b)
{
	queue<pair<int,int>> q;
	q.push({a,b});
	char mark = vec[a][b];
	vec[a][b] = 'X';
	while(!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(vec[x][y+1] == mark) {
			q.push({x,y+1});
			vec[x][y+1] = 'X';
		}
		if(vec[x+1][y] == mark) {
			q.push({x+1,y});
			vec[x+1][y] = 'X';
		}
		if(vec[x-1][y] == mark) {
			q.push({x-1,y});
			vec[x-1][y] = 'X';
		}
		if(vec[x][y-1] == mark) {
			q.push({x,y-1});
			vec[x][y-1] = 'X';
		}
	}
}
int main()
{
	int N, ans1=0,ans2=0;
	cin>>N;
	vector<vector<char>> vec(N+2, vector<char>(N+2,'X'));
	vector<vector<char>> vec2(N+2, vector<char>(N+2,'X'));
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++) {
			char c;
			cin>>c;
			if(c=='R')
			{
				vec[i][j] = 'R';
				vec2[i][j] = 'R';
			}
			else if(c=='G')
			{
				vec[i][j] = 'G';
				vec2[i][j] = 'R';
			}
			else if(c=='B')
			{
				vec[i][j] = 'B';
				vec2[i][j] = 'B';
			}
		}
	}
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			if(vec[i][j] != 'X') {
				BFS(vec,i,j);
				ans1++;
			}
			if(vec2[i][j] != 'X') {
				BFS(vec2,i,j);
				ans2++;
			}
		}
	}
	cout<<ans1<<" "<<ans2;
	return 0;
}

---

후기

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

처음에는 queue에서 pop할 때 방문 체크를 해줘서 중복 방문 때문에 메모리 초과 에러가 발생했다.

그래서 queue에 push하는 순간에 방문 체크를 해주는 방법으로 해결했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!