[Python] 토마토 - 백준 (BFS)

해당 글은 백준 7576번 문제 '토마토'를 다룬다.

문제

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

7576번: 토마토

 

설명

해당 문제는 BFS로 해결할 수 있는 문제이다.

n, m을 입력받을 때, 헷갈려서 c, r로 변수명을 바꿔서 입력받았다..!

주의할 점은 익은 토마토인 1의 모든 위치에서 바이러스처럼 전파되므로 queue에 익은 토마토의 위치를 모두 넣어준 상태에서 bfs를 진행해야한다.

 

코드

from collections import deque

c, r = map(int, input().split())
box = []
for i in range(r):
    box.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
q = deque()

def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= 0 and nx < r and ny >= 0 and ny < c:
                if box[nx][ny] == 0:
                    box[nx][ny] = box[x][y] + 1
                    q.append((nx, ny))


for i in range(r):
    for j in range(c):
        if box[i][j] == 1:
            q.append((i, j))

bfs()

zero_count = sum(box[i].count(0) for i in range(r))
if zero_count == 0:
    print(max(map(max, box)) - 1)
else:
    print(-1)