알고리즘: 백준 7576번 토마토 (feat.python)

 

7576번: 토마토

 

 

import sys
from collections import deque
read = sys.stdin.readline
x, y = list(map(int, read().split()))
box = []
q_y = deque()
q_x = deque()
for i in range(y):
    tmp = list(map(int, read().split()))
    box.append(tmp)
count_1 = 0
for i in range(len(box)):
    for j in range(len(box[0])):
        if box[i][j] == 1:
            q_y.append(i)
            q_x.append(j)
            count_1 += 1

def check(y, x):
    if 0<= y < len(box) and 0 <= x < len(box[0])  and box[y][x] == 0:
        return True
    else:
        return False



def bfs():
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    c = 0
    count = deque(0 for _ in range(count_1))
    while q_y and q_x:
        py = q_y.popleft()
        px = q_x.popleft()
        c = count.popleft()
        for i in range(4):
            if check(py + dy[i], px + dx[i]):
                q_y.append(py + dy[i])
                q_x.append(px + dx[i])
                box[py + dy[i]][px + dx[i]] = 1
                count.append(c + 1)

    return c

count = bfs()

if count != 0:
    answer = count
else:
    answer = 0
for sub in box:
    if 0 in sub:
        answer = -1
print(answer)