[ BOJ/C# ] 7576 토마토

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

7576번: 토마토

BFS 문제이다. 이전의 양배추에서 배운 내용을 기억해 내며 직접 풀어보았다. 

Queue를 2개 만들어 다음 날 검사할 좌표를 다른 큐에 넣어주었다. 

모두 0, -1, 1일 경우를 잘 체크해 주어야 한다. 

using System;
using System.IO;
using System.Text;

namespace B7576
{
    class Program
    {
        static int M, N;
        static int[,] map = new int[1001, 1001];
        static bool[,] visited = new bool[1001, 1001];
        static int[] dx = { -1, 1, 0, 0 };
        static int[] dy = { 0, 0, -1, 1 };
        static Queue<(int, int)> q = new Queue<(int, int)>();
        static Queue<(int, int)> qNext = new Queue<(int, int)>();
        static int day = -1;
        static void BFS()
        {
            //q혹은 qNext
            if (q.Count > 0)
            {
                while (q.Count > 0)
                {
                    var deq = q.Dequeue();
                    int deqx = deq.Item1;
                    int deqy = deq.Item2;
                    visited[deqx, deqy] = true;
                    for (int i = 0; i < 4; i++)
                    {
                        deqx = deq.Item1 + dx[i];
                        deqy = deq.Item2 + dy[i];

                        if (deqx < 0 || deqx >= N || deqy < 0 || deqy >= M) continue;
                        visited[deqx, deqy] = true;
                        if (map[deqx, deqy] == -1 || map[deqx, deqy] == 1) continue;
                        if (map[deqx, deqy] == 0)
                        {
                            map[deqx, deqy] = 1;
                            qNext.Enqueue((deqx, deqy));
                        }
                    }
                }
            }
            else
            {
                while (qNext.Count > 0)
                {
                    var deq = qNext.Dequeue();
                    int deqx = deq.Item1;
                    int deqy = deq.Item2;
                    for (int i = 0; i < 4; i++)
                    {
                        deqx = deq.Item1 + dx[i];
                        deqy = deq.Item2 + dy[i];
                        if (deqx < 0 || deqx >= N || deqy < 0 || deqy >= M) continue;
                        visited[deqx, deqy] = true;
                        if (map[deqx, deqy] == -1) continue;
                        else if (map[deqx, deqy] == 0)
                        {
                            map[deqx, deqy] = 1;
                            q.Enqueue((deqx, deqy));
                        }
                    }
                }
            }
        }
        static bool AllOK()
        {
            for (int x = 0; x < N; x++)
            {
                for (int y = 0; y < M; y++)
                {
                    if (visited[x, y] == false && map[x, y] == 0)
                        return false;
                }
            }
            return true;
        }
        static void Main()
        {
            StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            //입력
            int[] mn = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            M = mn[0];
            N = mn[1];
            bool isOK = false;  
            for(int i = 0; i < N; i++)
            {
                int[] input = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                for(int j = 0; j < M; j++)
                {
                    map[i,j] = input[j];
                    if (input[j] == 0) isOK = true;
                }
            }
            if (!isOK) sw.Write(0); //0인 토마토가 없는 경우
            else
            {
                for(int x = 0; x < N; x++)
                {
                    for(int y = 0; y < M; y++)
                    {
                        //토마토가 익어있고, 방문리스트에 없다면
                        if (map[x, y] == 1 && visited[x, y] == false)
                            q.Enqueue((x, y));
                    }
                }
                while(q.Count > 0 || qNext.Count > 0)
                {
                    day++;
                    BFS();
                }
                //모든 토마토가 익지 못하는 상황인가?
                if (!AllOK()) sw.Write(-1);
                else sw.Write(day);
            }
            sr.Close();
            sw.Flush();
            sw.Close();
        }
    }
}