백준 C# 7569 토마토 3차원

문제

익은 토마토를 기준으로 6방면의 토마토를 1일마다 전염시킴

1 : 익은 토마토

0 : 안익은 토마토

-1 : 없음

최초로 모든 토마토가 익는 날을 출력하되, 일부 토마토가 익을 수 없는 위치에 있는 경우 -1을 출력

 

해결

3차원 배열의 BFS 문제인데,
List<int> 1차원 배열로 평면화 시켜서 익은 토마토 기준으로 6방면의 토마토에 전파.

internal class E7569
{ // 토마토
    static void Main(string[] args)
    {
        string input() => Console.ReadLine();

        int[] MNH = input().Split().Select(int.Parse).ToArray();

        int m = MNH[0];

        List<int> list = new List<int>();

        //토마토의 값을 받아옵니다.
        for (int i = 0; i < MNH[1] * MNH[2]; 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;
        int floor = MNH[0] * MNH[1];

        while (sel.Count > 0)
        {
            //완성이 된 다음 한번 더 수행이 될 수 있다.
            if(!list.Contains(0)) { break; }

            //저장된 익은 토마토 위치 값만큼 반복한다.
            int count = sel.Count;
            for (int iter = 0; iter < count; iter++)
            {
                int id = sel.Dequeue();

                //각 상하 좌우 위 아래 인덱스 값을 계산한다. -1은 예외 값이다.
                int left = (id % m) == 0 ? -1 : (id -1);
                int right = (((id + 1) % (m)) == 0) ? -1 : (id + 1);

                int up = id % floor - m < 0 ? -1 : id - m;
                int down = (id + m) % floor < m ? -1 : id + m;


                int under = (id - floor) < 0 ? -1 : id - floor;
                int over = (id + floor) > (list.Count - 1) ? -1 : (id + floor);

                //지정된 인덱스 값을 기준으로 익은 토마토의 주변으로 전파
                int[] arr = new int[6] { left, right, up, down, under, over };
                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);
}}

id : 익은 토마토가 존재하는 Index

 

겪었던 반례

위 아래 값이 0이었던 경우[처음에는 모든 방면의 합이 -6이면 탐색을 종료함]

2 2 2
0 -1
-1 0
0 -1
-1 0

//정답 : -1
//오답 : 무한루프

리스트에 누적된 값을 그대로 사용했을 때 2가 나왔음

3 3 2
0 0 1
0 -1 0
1 0 0
0 1 0
-1 0 0
0 0 0

//정답 3
//오답 2