[C++] 백준 10026 - 적록색약

 

 

백준 10026 - 적록색약

 

 

적록색약 #flaticon

 

 

 

이 문제는 바보같은 나의 무지함으로 인해

메모리초과를 무려 5번이나 받은 문제이다.

 

 

아무리봐도, 로직이 맞는데 왜! 도대체 왜! 메모리 초과가 나는 것인가

계속 고민하다가 구글링을 했더니...

 

 

[ BFS는 큐에서 뺀 다음이 아닌, 큐에서 넣을 때 방문 체크를 해줘야 한다]는

나만 모르던 사실을 알게되었다.

 

 

눈물을 훔치고 코드를 수정했다.

중복되는 코드를 줄일 수 있겠지만

내가 내 코드를 알아보기 힘들어서 그냥 두기로... :(

 

 

오늘도 성장하는...알린이로...

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

// 상우하좌 방향
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

queue<pair<int, int>> q; // 탐색 큐
char place[101][101]; // 구역
bool visit[101][101]; // 방문 여부 체크
int n; // 한 변의 길이
int result = 0, colresult = 0; // 최종 구역 개수

void bfs(int x, int y, char val, int cnt, bool color)
{
	q.push(make_pair(x, y));
	visit[x][y] = true;

	while (!q.empty())
	{
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			// 다음 탐색할 좌표
			int nx = cx + dx[i];
			int ny = cy + dy[i];

			// 구역의 범위를 벗어날 경우
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)
				continue;

			// 이미 방문한 좌표일 경우
			if (visit[nx][ny] == true)
				continue;

			// 적록색약이 아닐 경우, 같은 색상일 때 큐에 삽입
			// 적록색약일 경우, Red와 Green을 같은 색으로 취급
			if (color == false)
			{
				if (place[nx][ny] == val)
				{
					q.push(make_pair(nx, ny));
					visit[nx][ny] = true;
				}
			}
			else
			{
				if (place[nx][ny] == val || ((val == 'R' && place[nx][ny] == 'G')
						|| (val == 'G' && place[nx][ny] == 'R')))
				{
					q.push(make_pair(nx, ny));
					visit[nx][ny] = true;
				}
			}
		}
	}
}

int solve(bool color)
{
	int cnt = 1;
	for (int x = 0; x < n; x++)
		for (int y = 0; y < n; y++)
			if (visit[x][y] == false)
				bfs(x, y, place[x][y], cnt++, color);
	return cnt - 1; // 증가된 1을 빼준 결과를 리턴
}

int main()
{
	scanf("%d", &n);

	// 사용자로부터 입력 받음
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf(" %c", &place[i][j]);

	result = solve(false); // 적록색약이 아닌 경우 탐색
	memset(visit, false, sizeof(visit)); // 방문 좌표 초기화
	colresult = solve(true); // 적록색약인 경우 결과 저장

	printf("%d %d", result, colresult);
}