문제
풀이 : 내가 작성한 코드
public static void Main()
{
int length = int.Parse(Console.ReadLine());
for (int i = 0; i < length; i++)
{
string[] str = Console.ReadLine().Split(' ');
int x = int.Parse(str[0]);
int y = int.Parse(str[1]);
int count = int.Parse(str[2]);
Queue<(int, int)> queue = new Queue<(int, int)>();
int[,] arry = new int[x, y];
int[,] vis = new int[x, y];
for (int k = 0; k < count; k++)
{
string[] strpos = Console.ReadLine().Split(' ');
arry[int.Parse(strpos[0]), int.Parse(strpos[1])] = 1;
}
int[] dx = new int[] { 1, 0, -1, 0 };
int[] dy = new int[] { 0, 1, 0, -1 }; // 상하좌우 네 방향을 의미
int nG = 0;
for (int z = 0; z < x; z++)
{
for (int v = 0; v < y; v++)
{
if (vis[z, v] == 1 || arry[z, v] == 0)
{
continue;
}
queue.Enqueue((z, v));
nG++;
while (queue.Count != 0)
{
var cur = queue.Dequeue();
int curx = cur.Item1;
int cury = cur.Item2;
//시작 확인
// 상하좌우 칸을 살펴볼 것이다.
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Item1 + dx[dir];
int ny = cur.Item2 + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
if (nx < 0 || nx >= x || ny < 0 || ny >= y)
continue; // 범위 밖일 경우 넘어감
if (vis[nx, ny] == 1 || arry[nx, ny] != 1)
continue; // 이미 방문한 칸이거나 배추칸이 아닐경우
vis[nx, ny] = 1; // (nx, ny)를 방문했다고 명시
queue.Enqueue((nx, ny));
}
}
}
}
Console.WriteLine(nG);
}
}BFS문제에서는 칸의 어떤 상태(배추:1,빈공간:0)인지 체크하는 부분과 큐에 들어간 칸(배추 가 심어져있는)이 어디까지 방문할수 있는지, 이미 방문한 위치인지 체크한다.
이문제는 흰지렁이가 포함할수 있는 범위를 묻는 문제는 아니고 몇개의 범위를 폼할수 있는 문제이기 때문에 큐에 입력될때 마다 카운팅을 했다.
문제
반응형
'알고리즘자료구조 > 알고리즘문제' 카테고리의 다른 글
| [백준] 알파벳 개수 10808 (0) | 2021.10.18 |
|---|---|
| [프로그래머스] [큐] 프린터 (0) | 2021.10.03 |
| [해커랭크] Caesar Cipher (0) | 2021.10.02 |
| 프로그래머스_C#)최대공약수와 최소공배수 (0) | 2019.09.12 |
| 프로그래머스_C#)제일 작은 수 제거하기 (0) | 2019.09.10 |
