[백준 7576번] 토마토

from collections import deque

# 가로(m), 세로(n)
m, n = map(int,input().split())

# 토마토가 담긴 상자(2차원 리스트)
area = []
# 토마토가 존재하는 위치를 담는 리스트
exist_list = []

# 토마도가 모두 익는 최소 일수(정답)
result = 0

# BFS 함수
def bfs(list):

  global result

  queue = deque(list)
    
  # 익을 수 있는 토마토가 다 익었을 때, 마지막 구역에 저장된 값
  depth = 0

  while queue:

    v = queue.popleft()

    nx = [-1,1,0,0]
    ny = [0,0,-1,1]

    for i in range(4):
      temp_x = v[0] + nx[i]
      temp_y = v[1] + ny[i]

      # 배열의 영역을 벗어났는지 / 다음 영역에 익지 않은 토마토가 있는지 확인
      if temp_x >=0 and temp_x < n and temp_y >= 0 and temp_y <m and area[temp_x][temp_y] == 0:
        # 조건을 만족하면 (현재 값 + 1) 저장
        area[temp_x][temp_y] = area[v[0]][v[1]] + 1
        depth = area[v[0]][v[1]] + 1
        # 큐에 삽입
        queue.append((temp_x,temp_y))

  # 1에서 부터 시작했기 때문에 정답은 (depth - 1)
  result = depth -1

# 토마토 위치 정보 입력받기
for _ in range(n):
  area.append(list(map(int,input().split())))

# 만약에 처음부터 모든 토마토가 익어있는 상태라면 0 출력
if all(0 not in l for l in area):
  print(0)

else:
  for i in range(n):
    for j in range(m):
      if area[i][j] == 1:
        exist_list.append((i,j))

  bfs(exist_list)

  # 시간이 지나도 토마토가 익지 못하는 경우 -1 출력
  if any(0 in l for l in area):
    print(-1)
  
  else:
    print(result)

이번 문제는 익은 토마토의 위치(1)에서 하루가 지날 때 마다 인접한 토마토(0)들이 익는다고 가정하고, 영역 내에 있는 토마토들이 모두 익기 위해서 걸리는 최소 시간을 구하는 문제이다.

 

다른 BFS 문제들과 차별화된 점이라고 한다면, 특정 지점에서부터 시작하는 것이 아니라 하루가 지날 때마다 익은 토마토들이 동시에 주변토마토에게 영향을 주기 때문에 BFS 함수의 인자를 특정 위치(x,y)가 아니라 위치 정보로 이루어진 배열(list)를 받아서 큐에 넣어준다는 것이다 !

 

이렇게 특정한 위치가 아니라 동시에 인접 영역에 영향을 주는 문제는 처음 접해봐서 그런지, 흥미롭게 느껴지기도 했고 생각해볼 시간이 조금 필요했던 문제였다 :)