백준 알고리즘 10026번 - 적록색약

dfs를 통해 풀어 볼 수 있는 문제.

처음에는 비정상인을 카운팅할때 로직을 하나 더 짜야하나 고민했지만,, 생각해보니 적록색약은 녹색과 빨간색을 구별하지 못한다.

따라서 모든 빨간색을 녹색으로 바꾸어놓고 풀거나, 모든 녹색을 빨간색으로 바꾸어 놓고 풀어도 정답은 동일하다.

그렇게 바꿔놓은 다음 dfs를 돌리자.

 

 

#include <iostream>
using namespace std;

int num,count=0;
char map[101][101];
bool visited[101][101];
//앞,뒤,위,아래로 이동가능
int dx[5]={0,-1,0,0,1};
int dy[5]={0,0,1,-1,0};

//이전에 방문한 것과 색깔이 동일하다면 그곳으로 이동한다.
void dfs(int startX,int startY)
{
	visited[startY][startX]=true;
	for(int i=1;i<=4;i++){
		int nowX=startX+dx[i];
		int nowY=startY+dy[i];
		if(nowX>0 && nowX<=num && nowY>0 && nowY<=num){
			if(map[nowY][nowX]==map[startY][startX]){
				if(!visited[nowY][nowX]){
					dfs(nowX,nowY);	
				}
			}
		}
	}		
}
//정상인 다 확인하고 비정상인 카운팅 하기전에 초기화
void init()
{
	count=0;
	for(int i=1;i<=num;i++){
		for(int j=1;j<=num;j++){
			visited[i][j]=false;
			if(map[i][j]=='G') map[i][j]='R';
		}
	}
}

int main() 
{
	cin>>num;
	for(int i=1;i<=num;i++){
		for(int j=1;j<=num;j++){
			cin>>map[i][j];
		}
	}
	//정상인의 시각에서 카운팅
	for(int i=1;i<=num;i++){
		for(int j=1;j<=num;j++){
			if(!visited[i][j]) {
				count++;
				dfs(j,i);
			}		
		}
	}
	cout<<count<<" ";
	//초기화한다.
	init();
	//비정상의 시각에서 카운팅한다
	for(int i=1;i<=num;i++){
		for(int j=1;j<=num;j++){
			if(!visited[i][j]) {
				count++;
				dfs(j,i);
			}		
		}
	}
	cout<<count;
}