[C#]백준 7576번: 토마토

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

7576번: 토마토

 

---

• 문제

---

• 문제풀이

visit을 만들어주어서 방문처리 후 숫자를 1로 바꿔준다. BFS를 마친 뒤 0이 있다면 -1을 출력해준다.

---

• 코드 1

using System;
using System.Collections.Generic;

namespace ConsoleApp2
{
    internal class Program
    {
        public static int[,] graph;
        public static int N, M;
        public static bool[,] visit;
        public static int[] dx = { -1, 1, 0, 0 };
        public static int[] dy = { 0, 0, 1, -1 };
        public static Queue<(int, int)> queue = new Queue<(int, int)>();

        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            M = input[0];
            N = input[1];
            graph = new int[N, M];
            visit = new bool[N, M];

            for (int i = 0; i < N; i++)
            {
                string[] str = Console.ReadLine().Split();
                for (int j = 0; j < M; j++)
                {
                    graph[i, j] = int.Parse(str[j]);
                    visit[i, j] = false;
                }
            }

            int days = bfs();

            
            bool all = true;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (graph[i, j] == 0)
                    {
                        all = false;
                        break;
                    }
                }
            }

            if (all)
                Console.WriteLine(days - 1);
            else
                Console.WriteLine(-1);
        }

        public static int bfs()
        {
            int days = 0;

          
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (graph[i, j] == 1)
                    {
                        queue.Enqueue((i, j));
                        visit[i, j] = true;
                    }
                }
            }

            while (queue.Count > 0)
            {
                int size = queue.Count;

                for (int i = 0; i < size; i++)
                {
                    (int a, int b) = queue.Dequeue();

                    for (int k = 0; k < 4; k++)
                    {
                        int x = a + dx[k];
                        int y = b + dy[k];
                        if (x >= 0 && x < N && y >= 0 && y < M)
                        {
                            if (!visit[x, y] && graph[x, y] == 0)
                            {
                                visit[x, y] = true;
                                graph[x, y] = 1; 
                                queue.Enqueue((x, y));
                            }
                        }
                    }
                }

                days++;
            }

            return days;
        }
    }
}

 

---

• 후기

예전에 좀비에 전염된다는 문제를 풀었던 코드가 있어 일부 수정했다.