백준(BOJ) 7576 토마토(Python)

문제 내용

BFS 문제.

queue에서 좌표를 한 번 꺼내고, 주변 토마토를 익게 한 다음 현재 익은 토마토의 개수가 전체 토마토의 개수와 같다면 break한다.

만약 위에서 break하지 못했다면 이는 모든 토마토를 익게할 수 없는 경우이다.

그 외에는 while문을 돌기 전 현재 익은 토마토의 개수와 전체 토마토의 개수가 같다면 0을 출력한다.

​

코드는 다음과 같다.

​

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
from itertools import permutations
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

m,n=map(int,input().split())
L=[]
c=0
a=m*n
dx=[1,-1,0,0,0,0]
dy=[0,0,1,-1,0,0]
queue=deque()
visited=[[0]*m for i in range(n)]
L=[]
for j in range(n):
    A=list(map(int,input().split()))
    for k in range(m):
        if A[k]==1:
            queue.append([j,k,0])
            visited[j][k]=1
            c+=1
        elif A[k]==-1:
            a-=1
    L.append(A)
if c!=a:
    flag=0
    while queue:
        x,y,k=queue.popleft()
        for i in range(6):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if L[nx][ny]==0 and not visited[nx][ny]:
                    queue.append([nx,ny,k+1])
                    visited[nx][ny]=1
                    c+=1
        if c==a:
            flag=k+1
            break
    if c!=a:
        print(-1)
    else:
        print(flag)
else:
    print(0)