토마토 풀이

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

백준 알고리즘 기초 2/2 600에서 8번째 - 7576번 토마토를 풀어보았다.

 

풀이: https://jiwon-coding.tistory.com/97 를 참고했다.

 

C++

 

Python

from collections import deque

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

m,n=map(int,input().split())
graph=[list(map(int,input().split())) for i in range(n)]
bfs()
res=0
for i in graph:
	for j in i:
		if j==0:
			print(-1)
			exit(0)
	res=max(res,max(i))
print(res-1)

Java