[백준] 7576번 토마토 (python 파이썬)

문제

7576번: 토마토

 

사용 알고리즘

- bfs

 

생각해보아야 할 것

1. 토마토가 익는 것을 구현하기

 - 익은 토마토에 대하여 bfs을 진행

 - 인접한 토마토에 대하여 익으므로 bfs을 이용하여 구현
 - 맨 처음 익은 토마토를 큐에 추가

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

2. 최대 일 구하기

- G의 값은 익는 데 걸리는 일수 + 1를 의미함

- 익은 토마토가 있다면 G값중 가장 큰 값 -1 출력

- 만약 익은 토마토가 없는 경우(모든 G의 값이 0인 경우) -1 출력 

# 익지 않은 토마토가 있는 지 , 최대 일 수 확인
for i in range(N):
    for j in range(M):
        if  G[i][j] == 0:
            is_zero = True
        max_days = max(max_days,G[i][j])
if is_zero:
    print(-1)
else:
    print(max_days-1)

 

 

전체코드

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

M, N = map(int,input().split())
G = []
for _ in range(N):
    G.append(list(map(int,input().split())))
Q = deque()
# 처음 익은 토마토는 큐에 추가
for i in range(N):
    for j in range(M):
        if G[i][j] == 1:
            Q.append((i,j))
mx_list = [-1,1,0,0]
my_list = [0,0,1,-1]
while Q:
    x,y = Q.popleft()
    
    for mx,my in zip(mx_list,my_list):
        nx = x + mx
        ny = y + my
        if 0<=nx <N and 0<=ny<M and G[nx][ny]== 0  : # 익지 않았다면
            Q.append((nx,ny))
            G[nx][ny] = G[x][y]+1 # days +1
            
max_days = 0
is_zero = False

# 익지 않은 토마토가 있는 지 , 최대 일 수 확인
for i in range(N):
    for j in range(M):
        if  G[i][j] == 0:
            is_zero = True
        max_days = max(max_days,G[i][j])
if is_zero:
    print(-1)
else:

결과