C++ / 10026 / 적록색약 ( 너비 우선 탐색 )

https://www.acmicpc.net/problem/10026

문제 요약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못합니다.

n * n 크기의 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있습니다.

그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있습니다. 또 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속합니다. (색약인은 R과 G도 같은 색상이라 합니다.)

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

위에 같은 경우는 일반인은 4개, 색약인은 3개의 구역으로 구분 할 수있습니다.

문제 풀이

1. 그리드를 입력받을 백터를 만듭니다.

2. 정상인인 경우, 색약인인 경우 방문체를 위한 백터를 만듭니다.

3. 그리드를 입력 받습니다.

4. 정상인 bfs 함수를 만듭니다. 인자로는 탐색을 시작할 좌표와, 기준이 될 색깔을 입력받습니다.

5. 기본적이 bfs 로직이지만 다음 인덱스를 탐색하는 기준으로는  기준이 될 색깔과 현재 같은 색깔인지 확인하도록 합니다.

6. 두 함수 모두 함수가 종료될때 ( 같은 색 묶음 탐색이 끝남 ) cnt를 증가 시켜줍니다.

7. 색약인 bfs 함수를 만듭니다. 위에 정상인 함수와 같지만 R, G는 같은 색으로 처리하게 조건을 줍니다.

8. 다시 메인 함수에서 그리드 크기만큼 반복문을 만들어서 정상인과 색약인의 방문하지 않은 노드들을 탐색 시켜줍니다.

9. cnt를 출력합니다.

주의할 점

이 문제는 bfs와 dfs 알고리즘을 사용하여 풀어야 하는 문제입니다.

bfs가 dfs보다 시간복잡도가 높아 dfs를 사용하는 것이 좋으나 저는 bfs가 조금 더 익숙한 관계로 bfs로 풀게 되었습니다.

방문 횟수를 함수 별로 만들어 주어야 하기때문에 visit를 2개 만들어 주었습니다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>


using namespace std;



vector<vector<char>> v;
// 정상인 방문 체크
vector<vector<bool>> visit;
// 색약 방문 체크
vector<vector<bool>> visit2;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int n, cnt1 = 0, cnt2 = 0;

// 정상인 경우
void bfs1(int x, int y, char color)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = 1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int xx = dx[i] + x;
			int yy = dy[i] + y;


			if (xx >= n || xx < 0 || yy >= n || yy < 0)
			{
				continue;
			}

			// 현재 색이랑 같은 색일 때만 진행
			if (!visit[xx][yy] && v[xx][yy] == color)
			{
				visit[xx][yy] = 1;
				q.push(make_pair(xx, yy));
			}

		}
	}
	cnt1++;
}

// 색약인 경우
void bfs2(int x, int y, char color)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit2[x][y] = 1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int xx = dx[i] + x;
			int yy = dy[i] + y;


			if (xx >= n || xx < 0 || yy >= n || yy < 0)
			{
				continue;
			}

			// 색약은 적색과 녹색을 같이 진행
			if (color == 'R' || color == 'G')
			{
				if (!visit2[xx][yy] && v[xx][yy] == 'R')
				{
					visit2[xx][yy] = 1;
					q.push(make_pair(xx, yy));
				}
				if (!visit2[xx][yy] && v[xx][yy] == 'G')
				{
					visit2[xx][yy] = 1;
					q.push(make_pair(xx, yy));
				}
			}
			// 청색일 경우
			if (color == 'B')
			{

				if (!visit2[xx][yy] && v[xx][yy] == color)
				{
					visit2[xx][yy] = 1;
					q.push(make_pair(xx, yy));
				}
			}
		}
	}
	cnt2++;
}


int main()
{
	cin >> n;
	v.resize(n, vector<char>(n));
	visit.resize(n, vector<bool>(n));
	visit2.resize(n, vector<bool>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			// 방문하지 않은 경우 정상인
			if (!visit[i][j])
			{
				bfs1(i, j, v[i][j]);
			}
			// 방문하지 않은 경우 색약
			if (!visit2[i][j])
			{
				bfs2(i, j, v[i][j]);
			}
		}
	}

	cout << cnt1 << " " << cnt2;
	return 0;
}

반응형

예제

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

결과