📌 [BOJ] 백준 7576 토마토

📖 문제

📖 예제

📖 풀이

from collections import deque
import sys

M, N = map(int, input().split())
graph = []
for _ in range(N):
  graph.append(list(map(int, sys.stdin.readline().split())))

queue = deque()
dx = [0,0,1,-1]
dy = [1,-1,0,0]

for i in range(N):
  for j in range(M):
    if graph[i][j] == 1:
      queue.append((i,j))

def BFS():
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx<0 or nx>=N or ny<0 or ny>=M:
        continue
      elif graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx,ny))

BFS()
answer = 0
for i in range(N):
  for j in range(M):
    if graph[i][j] == 0:
      print(-1)
      exit()
    else:
      answer = max(answer, graph[i][j])

print(answer-1)

우선 graph에서 값이 1인 위치를 모두 자료 구조 큐에 넣은 뒤 BFS를 통해 그것들의 주위 값인 0들을 한 번의 step을 기준으로 +1씩 올려준다.
그럼에도 graph내에 0의 값이 존재한다면 -1을 출력하며 실행을 중지한다.
만약 0이 없다면 graph에서 가장 큰 값의 -1을 출력한다.