[백준 7576] 토마토

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

7576번: 토마토

▶ 서로 다른 여러점에서, 동시에 물들여서 며칠이 걸리는지 알아내는 문제 

▶ 코드 ( 큐 ver. )

# 예외처리가 중요
# 예외1)) 다 물들였는데, 0 남아있는 경우 : -1 출력
# 예외2)) 애초에 0원소가 없는경우 : 0 출력 


from collections import deque

m,n = map(int, input().split()) # m: 가로, n: 세로
myMap = []
ripe = deque() # 익은 토마토 위치 

for i in range(n):
    row = list(map(int, input().split()))
    for j in range(m):
        if row[j] == 1:
            ripe.append([i,j])
    myMap.append(row)
#print(myMap)
#print(ripe) # deque([[0, 0], [3, 5]])

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

#visited = [[0]*m for _ in range(n)] # 필요 X

def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs():
    
    days = -1

    while ripe:
        days += 1
        for _ in range(len(ripe)):  # 현재 ripe의 원소 개수만큼만 반복 !! ★
            x, y = ripe.popleft()   # [0,0], [3,5] 까지만  

            tx = 0
            ty = 0
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]

                if isInGraph(tx, ty):
                    if myMap[tx][ty] == 0: # [tx, ty] not in ripe 조건 추가하면 시간초과
                        myMap[tx][ty] = 1
                        ripe.append([tx,ty])

    # 예외1)) 
    for row in myMap:
        if 0 in row:
            return -1
    return days
        

print( bfs() )
#print(myMap)

#참조: https://dojinkimm.github.io/problem_solving/2019/11/03/boj-7576-tomato.html

 

※ python3로 채점해야 메모리초과 X

※ 방문한 myMap의 원소를 0 -> 1로 바꿔주므로, visited를 통한 방문처리 필요 X

※ [tx, ty] not in ripe 조건 추가하면 시간초과