[Python]DFS와BFS 백준 7576

 문제

 https://www.acmicpc.net/problem/7576

이 문제도 bfs를 통해 풀수있다.

처음에 익은 토마토를 모두 넣어주면된다.

큐가 빌때까지 반복하고 모든 토마토가 익어있을때와 모두 익지 못하는상황도 잘처리

해준다.

import sys
from collections import deque
 
def box(ripens,N,M,unripen,empty):
    if len(ripens)==N*M-empty:#처음부터 모든 토마토가 익어있다면
        return 0
 
    q=deque()
    for ripen in ripens:#익은 토마토의 위치 모두 넣어줌
        q.append(ripen)
    day=0#날짜 저장
    unripencount=0#익힌토마토수
    while q:
        [x,y]=q.popleft()
        dx=[0,1,0,-1]#왼쪽 아래쪽 오른쪽 위쪽
        dy=[-1,0,1,0]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and tomato[nx][ny]==0:
                tomato[nx][ny]=tomato[x][y]+1
                day=tomato[nx][ny]
                q.append([nx,ny])
                unripencount+=1#익힌토마토 추가
 
 
    if unripen==unripencount:#익힌토마토 수와 안익었던토마토 수가 일치하면
        return day-1#모두 익을때까지의 날짜
    else:#다르면 안익은 토마토가 남아있다는것
        return -1
 
 
 
M,N=map(int,sys.stdin.readline().split())
tomato=[]
for _ in range(N):
    tmp=list(map(int,sys.stdin.readline().split()))
    tomato.append(tmp)
 
 
ripen=[]#익은토마토
unripen=0
empty=0
for i in range(N):#모든 익은 토마토 찾기
    for j in range(M):
        if tomato[i][j]==1:#익은 토마토위치 모두저장
            ripen.append([i,j])
        elif tomato[i][j]==0:#안익은 토마토 개수 체크
            unripen+=1
        elif tomato[i][j]==-1:
            empty+=1
 
 
 
result=box(ripen,N,M,unripen,empty)
if result==0:
    print(0)
elif result==-1:
    print(-1)
else:
    print(result)