[Python] 백준 #7576 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

제일 중요한 것은 문제를 이해하는 것 & 반례를 찾는 것 이라고 생각한다.

코드 짜기 전에 문제 완벽하게 이해하고 테스트 케이스 꼼꼼하게 찾아보기.

from collections import deque

que=deque()
m,n=map(int,input().split())
graph=[]

visited=[[] for i in range(n)]
for i in range(n):
    for j in range(m):
        visited[i].append(0)


cnt=0

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

#그래프 생성
for i in range(n):
    graph.append(list(map(int,input().split())))
    
    
l_list=[]
for i in range(n):
    for j in range(m):
        #익은 토마토가 존재할때        
        if(graph[i][j])==1:
            l_list.append([i,j])
            visited[i][j]=1 #방문 처리
que.append(l_list)
            
while que:
        q=que.popleft()
        l_list=[]
                
        for k in range(len(q)):
            x=q[k][0]
            y=q[k][1]
                    
                    
            for e in range(4):
                xx=x+dx[e]
                yy=y+dy[e]
                        
                if(xx>=0 and yy>=0 and xx<n and yy<m):
                    if(graph[xx][yy]==0 and visited[xx][yy]==0):
                        l_list.append([xx,yy])
                        visited[xx][yy]=1
                        graph[xx][yy]=1 #익은 토마토로 변경
                                
        if l_list: #비어있지 않으면               
            que.append(l_list)
            cnt+=1
result=0
check=0
for i in range(n):
    for j in range(m):
        if graph[i][j]==0 : #하나라도 안 익은 토마토 있으면
            check=-1
            break
            
        elif graph[i][j]!=0:
            result+=1 # 토마토 원래 없었던 부분이랑 익은 토마토 개수 합쳐주기
            
if check== -1:
    print(-1)
    
elif result== n*m and cnt!=0:
    print(cnt)
    
else:
    print(0)