백준 #1776. 토마토: BFS/ 골드5

문제 링크 : https://www.acmicpc.net/problem/7576

🔍 Inspection

문제 접근

• 유형 : BFS - 확산 최소 시간 = 최단 거리

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. BFS준비 단계 : 익은 토마토 위치(=field[][] = 1)인 위치에서 부터 시작
2. 안 익은 토마토 확산 시키기 by bfs
   • field의 값 업데이트 - 토마토가 익은 시간
3. 출력
   1. 다 익음 : field 값 중 최대값 = 마지막에 익은 토마토
   2. 남음 : field 값 중 안 익은(0) 토마토 존재함

🚩제출한 코드

import sys
from collections import deque
#[0] 입력 변수 
input = sys.stdin.readline
N,M = map(int, input().split())
field = [list(map(int,input().split())) for _ in range(M) ]
dy = [-1,1,0,0]
dx = [-0,0,-1,1]

# [1] BFS 초기값 -초기 field에 서 익은 토마토 위치 q에 넣기
q = deque()
for m in range(M) :
        for n in range(N) :
            # print(m , n)
            if field[m][n] == 1: 
                # 안 익은 토마토 익히기 
                q.append([m,n])
                
while q :
    #[2] 익은 토마토 확산시키기
    y,x = q.popleft()
    for d in range(4):
        ny = y + dy[d] ; nx = x + dx[d]
        if 0<= ny <M and 0 <= nx < N and field[ny][nx] == 0:
            # 토마토가 익은 시간때를 filed 값으로 표기
            field[ny][nx] = field[y][x] +1 
            q.append([ny,nx])

#[3] 출력 형태 지정 
# 실패한 경우 : field에 안 익은 토마토(=0) 이 남은 경우
# 성공한 경우 : 다 익은 최소 시간 ==  field에 있는 값(: 익은 시간때) 중 최대값 -1         
max_num = 0 
for i in range(M) :
    for j in range(N):
        if field[i][j]== 0 : 
            print(-1)
            exit()
        max_num = max(max_num , field[i][j])
print(max_num-1)

• 💥 1차 제출

🚩결과