기타/백준
백준 C# 7576 토마토 2차원
Krapboss
2024. 7. 31. 19:16
https://krapboss.tistory.com/120
문제
익은 토마토를 기준으로 4방면의 토마토를 1일마다 전염시킴
1 : 익은 토마토
0 : 안익은 토마토
-1 : 없음
최초로 모든 토마토가 익는 날을 출력하되, 일부 토마토가 익을 수 없는 위치에 있는 경우 -1을 출력
해결
2차원 배열의 BFS 문제인데,
List 1차원 배열로 평면화 시켜서 익은 토마토 기준으로 4방면의 토마토에 전파.
internal class E7576_토마토_2차원
{ // 토마토
static void Main(string[] args)
{
string input() => Console.ReadLine();
int[] MN = input().Split().Select(int.Parse).ToArray();
int m = MN[0];
List<int> list = new List<int>();
//토마토 박스 값 추가
for (int i = 0; i < MN[1]; i++)
{
list.AddRange(input().Split().Select(int.Parse));
}
//익은 토마토의 인덱트 저장
Queue<int> sel = new Queue<int>();
if (list.Contains(0))
{
for (int i = 0; i < list.Count; i++)
{
if (list[i] == 1) sel.Enqueue(i);
}
}
int days = 0;
while (sel.Count > 0)
{
if(!list.Contains(0)) { break; }
int count = sel.Count;
for (int iter = 0; iter < count; iter++)
{
int id = sel.Dequeue();
//각 4방면의 인덱스를 구합니다.
int left = (id % m) == 0 ? -1 : (id -1);
int right = (((id + 1) % (m)) == 0) ? -1 : (id + 1);
int up = id - m < 0 ? -1 : id - m;
int down = (id + m) >= list.Count ? -1 : id + m;
//각 4방면 인덱스에 익은 토마토를 전파합니다.
int[] arr = new int[4] { left, right, up, down };
for (int j = 0; j < arr.Length; j++)
{
if (arr[j] != -1)
{
if (list[arr[j]] == 1 || list[arr[j]] == -1) continue;
list[arr[j]] = 1;
sel.Enqueue(arr[j]);
}
}
}
days++;
}
if (list.Contains(0)) Console.WriteLine(-1);
else Console.WriteLine(days);
}
}