[백준] 7576번 토마토

from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(m):
    graph.append(list(map(int, input().split())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])
count = 0
before = 0
for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            queue.append([i, j])
bfs()
max_ = 0

for i in range(m):
    maxtmp = max(graph[i])
    if 0 in graph[i]:
        max_ = 0
        break
    if maxtmp > max_:
        max_ = maxtmp
print(max_-1)

DFS로는 풀 수 없고 BFS로만 풀 수 있는 문제.

DFS로 풀 수 없는 이유는, 하나의 1에서 시작하면 한없이 깊이 파고 들어서 여러개의 1(토마토)가 있을 때에도 하나의 1에 대해서 깊이 하고 들기 때문이다.