[백준 BOJ_7576] 토마토 Python 풀이

출처: 백준 온라인 저지

문제

풀이

BFS를 이용하여 풀어주었습니다.

시작하기 전 익지 않은 토마토의 수를 세어주어 cnt에 저장해주었습니다. 익지 않은 토마토가 없다면 바로 0을 출력하게 했습니다. 또한 세어줄 때 익은 토마토의 좌표를 queue에 담아주었고, 익지 않은 토마토가 있다면 BFS를 돌아주는 방식으로 풀었습니다.

새로 익는 토마토 좌표에(box[ny][nx]) 익은 토마토 좌표(box[y][x]) 값에 1을 더한 값으로 계속 누적해주어 일수를 체크해주었습니다. queue에 새롭게 익은 토마토 좌표를 넣어줄 때 cnt 수도 감소 시켜주어 후에 토마토가 모두 익지 못하는 상황도 체크할 수 있게 하였습니다.

토마토가 모두 익었을 때(cnt == 0)는 box를 돌아주어 가장 큰 값의 1을 뺀 값이 최소 일수가 됩니다. 처음부터 이미 익은 토마토의 값(1)에 1을 더한 값으로 계속 누적해주었기 때문에 실제 최소 일수보다 하루 더 큰 값이 저장되기 때문입니다.

코드

from collections import deque

M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]
queue = deque()

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

result = -1
cnt = 0
for i in range(N):
  for j in range(M):
    if box[i][j] == 1:
      queue.append((i, j))
    elif box[i][j] == 0:
      cnt += 1

if cnt:    
  while queue:
    y, x = queue.popleft()
    if not cnt:
      break
    for i in range(4):
      ny, nx = y+dy[i], x+dx[i]
      if 0 <= ny < N and 0 <= nx < M and box[ny][nx] == 0:
        box[ny][nx] = box[y][x] + 1
        queue.append((ny, nx))
        cnt -= 1
  if not cnt:
    for i in range(N):
      result = max(result, max(box[i]))
    result -= 1
  # print(*box, sep="\n")
  print(result)
else:
  print(0)