> 문제 <

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

> 입력 / 출력 <

입력

1번째 줄 -> M: 상자의 가로 칸의 수, N: 상자의 세로 칸의 수 (단, 2 ≤ M, N ≤ 1000)
2번째 줄 -> 상자에 담긴 토마토들의 정보
0 = 익지 않은 토마토
1 = 익은 토마토
-1 = 토마토가 들어있지 않은 칸

출력

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

> 아이디어 <

초안

입력받은 행렬 요소가 1이나 -1로 이루어져있는가? ---> 0 출력
1이 왼,오,앞,뒤에 있는가? --> 현재 자리의 토마토는 다음날 익음 (day 카운트)
연산 후, 행렬 전체의 요소가 다 1이 아닌가? ---> -1 출력
------> BFS 사용할 생각을 못하고 반복문만을 이용해 문제를 해결하려했으나 너무 복잡해졌다.

해결 아이디어

BFS(너비 우선 탐색) 사용
큐(Queue)를 이용하며 한번 큐에 방문한 노드는 탐색하지 않는다.
현재 위치에서 델타 x,y를 사용해 상하좌우를 확인한다.
초깃값이 1로 설정된 (이미 익은 사과) 요소들의 index값을 큐에 넣어주고, 그 요소들의 주변부로 1을 전파해나간다.
하지만 이때, 현 요소의 상하좌우가 행렬을 벗어나면 안되므로 index 제한(if~)을 둔다.

> 코드 <

import sys
from collections import deque
r = sys.stdin.readline

def bfs(M, N, box):
    dx = [0, 0, -1, 1]  # 좌우
    dy = [-1, 1, 0, 0]  # 상하

    day = -1  # 이미 다 익은 상태면 0이 출력되어야 하므로
    while ripe:
      day += 1
      for _ in range(len(ripe)):
          x, y = ripe.popleft()

          for i in range(4):
              nx = x + dx[i]
              ny = y + dy[i]

              if (0 <= nx < N) and (0 <= ny < M) and (box[nx][ny] == 0):
                  box[nx][ny] = box[x][y] + 1
                  ripe.append([nx, ny])  # 새롭게 익은 토마토 위치 큐에 삽입 
                  
    #while ripe 연산이 끝난 후   
    for b in box:
      if 0 in b:  # 하나라도 안 익었는가?
        return -1
    return day

M, N = map(int, r().split())
box = [[int(x) for x in r().split()] for y in range(N)]
ripe = deque()
for x in range(len(box)):
    for y in range(len(box[x])):
        if box[x][y] == 1:
            ripe.append([x,y])  # 익은 토마토 위치 큐에 삽입

print(bfs(M, N, box))

아이디어 출처 : https://itadventure.tistory.com/34
코드 참고 출처 : https://devjin-blog.com/boj-7576-tomato/