기타/백준
백준 C# 10026 적록색약
Krapboss
2024. 8. 1. 22:09

문제
주어진 NxN 배열에서의 인접한 같은 문자끼리를 하나의 그룹으로 본다.
총 문자는 R G B 세가지가 존재하며,
일반적인 사람은 R G B 를 각 그룹으로 분리되고
적록색약인 사람은 RG, B 로 두 그룹으로 분리한다.
그때, 각 케이스가 인지하는 그룹의 수는?
해결
DPS 재귀함수를 사용하여
판단한 자리를 NxN 배열에 저장하며 지나감
internal class E10026_적록색약
{
static void Main(string[] args)
{
//4방향 정의
int[] dx = new int[] { -1, 1, 0, 0 };
int[] dy = new int[] { 0, 0, -1, 1 };
//같은 색상 탐색을 위한 재귀함수
void BPS(char[][] a, bool[,] c, int x, int y)
{
if (c[x, y]) return;
c[x, y] = true;
int len = a[0].Length;
for(int i = 0; i < 4; i++)
{
int X = x + dx[i];
int Y = y + dy[i];
if (X < 0 || Y < 0 || X >= len || Y >= len) continue;
if (a[x][y] == a[X][Y])
{
BPS(a, c, X, Y);
}
}
}
string input() =>Console.ReadLine();
int n = int.Parse(input());
char[][] arr = new char[n][];
bool[,] check = new bool[n,n];
//D => 적록 | S => 정상 시야
int D = 0, S = 0;
for(int i =0;i < n; i++)
{
arr[i] = input().Select(x=> x).ToArray();
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n; j++)
{
if (!check[i, j])
{
S++;
BPS(arr,check,i,j);
}
}
}
//G 를 R 로 변환 후 재탐색
check = new bool[n, n];
arr = arr.Select(x=> x.Select(y => y.Equals('G') ? 'R' : y).ToArray()).ToArray();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!check[i, j])
{
D++;
BPS(arr, check, i, j);
}
}
}
Console.WriteLine($"{S} {D}");
}
}