10026번 - 적록색약 c++

문제 설명

---

---

구역의 수를 묻는 그래프 탐색 문제 입니다.

BFS 알고리즘만 이용하면 됩니다. (단, 메모리 초과 에러를 조심하세요)

다른 분들은 memset 함수를 이용해 visited배열을 초기화 시키셨던데 메모리 시간 차이가 많이 안나길래 저는 그냥 for문으로 초기화 시켰습니다.

 

BFS를 한 번 돌면서 정상인과 적록색약의 답 모두 구하는 걸 고민했지만 N의 최대 크기($1 <= N <= 100$)가 크지않기에 시간 초과 걱정은 없었습니다.

 

전체적인 과정은

정상인이 보는 그림 BFS -> 정상인이 보는 그림의 구역 구하기 -> visited배열 초기화 -> 적록색약자가 보는 그림으로 변환(R과 G를 한가지 색상으로 통일) -> BFS -> 적록색약이 보는 그림의 구역 구하기

 

 

 

코드

---

#include<iostream>
#include<queue>
#include<cstring>

int N;
std::queue<std::pair<int, int> > q;
char picture[101][101];
int visited[101][101];

//방문여부가 저장되어있는 배열을 초기화 시키는 함수
void clean_visited()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			visited[i][j] =0;
		}
	}
}

//BFS알고리즘
void BFS(int x, int y)
{
	int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

	q.push(std::make_pair(x, y));
	
	if(visited[x][y])
		return;
	
	while(!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		
		q.pop();
		
		visited[x][y] = 1;
		for(int i=0; i<4; i++)
		{
            int next_x = x + dx[i];
            int next_y = y + dy[i];
			
			if(next_x < 0 || next_y < 0 || next_x > N-1 || next_y > N-1)
				continue;
			
			if(picture[next_x][next_y] == picture[x][y] && visited[next_x][next_y] == 0)
			{
				visited[next_x][next_y] = 1; //방문 표시를 안하면 메모리초과가 뜸!
				q.push(std::make_pair(next_x, next_y));
			}
		}
	}
}

int main()
{

    int result1 = 0, result2 = 0;
	
    std::cin >> N;
	std::string s;
	
    //문자열로 받고 한글자씩 배열에 저장
	for(int i=0; i<N; i++)
	{
		std::cin >> s;
		for(int j=0; j<N; j++)
		{
			picture[i][j] = s[j];
		}
	}
	

	모든 경우를 순회하며 BFS
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(!visited[i][j])
			{
				BFS(i, j);
				result1 += 1;
			}
		}
	}
	
	//visited배열 초기화
	clean_visited();
	
    //적록색약 시점으로, G을 R로 변경
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(picture[i][j] == 'G')
				picture[i][j] = 'R';
		}
	}
	
    //BFS
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(!visited[i][j])
			{
				BFS(i, j);
				result2 += 1;
			}
		}
	}
	std::cout << result1 << ' ' << result2;

	return 0;
}