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

문제 풀이

이 문제는 전형적인 BFS와 DFS 문제이며 DFS로 문제를 풀도록 하겠다.

예시의 부분은 아래와 같다.

R	R	R	B	B
G	G	B	B	B
B	B	B	R	R
B	B	R	R	R
R	R	R	R	R

예를 들면 첫 번째 [1,1], [1,2], [1,3] 영역을 칠하게 된다. 어떠한 식으로 칠해야할까?

1) for문으로 모든 영역을 훑도록 한다. (visit 체크된 좌표는 이미 칠했으므로 넘어간다.)

2) [1,1]이 입력되면 해당 좌표를 방문하였으므로 visit 체크한다.

3) 상하좌우 탐색한다.

4) 범위 밖으로 나가면 넘어간다.

5) 색이 다르는 등의 조건이 맞지 않는 경우 넘어간다.

6) 연결된 부위에서 조건이 맞는 내용은 또 칠한다. (DFS 함수에 탐색된 좌표를 다시 넣는다.)

 

위와 같다. 대부분 DFS 문제가 위 내용에서 크게 벗어나지는 않는다.

이 문제는 색맹인 사람과 아닌 사람이 있으므로 이에 맞게 R과 G에 대한 조건을 바꿔주면 된다.

결국 visit 체크하는 부분과 조건이 맞았을 때 다시 DFS 함수를 부르는 것이 요점이다.

 

소스코드

#include <iostream>
#include <vector>
#define MAX 101
using namespace std;

int n, map_idx;
char map[MAX][MAX];

int visit_noweak[MAX][MAX];
int visit_weak[MAX][MAX];

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

void input()
{
	cin>>n;
	
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			cin>>map[i][j];
		}
	}
}

bool inrange(int x, int y)
{
	return (x>=1 && y>=1 && x<=n &&y<=n);
}

void noweakness(int x, int y, char color)
{
	visit_noweak[x][y]=1;
	for (int d=0; d<4; d++)
	{
		int nx=x+dx[d];
		int ny=y+dy[d];
		
		if (inrange(nx,ny)==0) continue;
		if (visit_noweak[nx][ny]==1) continue;
		if (map[nx][ny]!=color) continue;
		
		noweakness(nx, ny, color);
	}
}

void weakness(int x, int y, char color)
{
	visit_weak[x][y]=1;
	for (int d=0; d<4; d++)
	{
		int nx=x+dx[d];
		int ny=y+dy[d];
		
		if (inrange(nx,ny)==0) continue;
		if (visit_weak[nx][ny]==1) continue;
		if ((color=='B' && map[nx][ny]!='B')||(color=='R' && map[nx][ny]=='B') || (color=='G' && map[nx][ny]=='B')) continue;
		
		weakness(nx, ny, color);
	}
}
			
int main()
{
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	
	input();
	int idx=0;
	int idx2=0;
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			if (visit_noweak[i][j]==false)
			{	
				noweakness(i,j,map[i][j]);
				idx++;
			}
		}
	}
	
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=n; j++)
		{
			if (visit_weak[i][j]==false)
			{
				weakness(i,j,map[i][j]);
				idx2++;
			}
		}
	}
	
	cout<<idx<<" "<<idx2;
	
	return 0;
}