[백준/#7576] 토마토 (Python)

문제 설명

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

7576번: 토마토

 

 

 

---

문제풀이

BFS로 거리를 재는 것은 기본적인 개념인데, 이를 활용하면 쉽게 해결할 수 있었다.

그러나 이 문제에서는 시작점이 여러 개 일 수 있다...

시작점이 여러 개인 BFS는 시작점을 큐에 모두 넣고 시작하면 된다!!

 

from collections import deque

N, M = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(M)]
dq = deque()
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for i in range(M):
    for j in range(N):
        if box[i][j] == 1:
            dq.append((i,j))

def bfs(q):
    temp = 0
    result = 0
    for b in box:
        temp += b.count(0)
    if temp == 0:
        return 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            if box[nx][ny] == -1:
                continue
            if box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                q.append((nx,ny))

    for b in box:
        if 0 in b:
            return -1
        result = max(max(b),result)

    return result-1



print(bfs(dq))