BOJ [토마토]

문제

문제 보기

다음과 같은 상자안에 토마토를 보관한다. 익은 토마토, 안익은 토마토, 빈 칸 세 종류가 있다. 안익은 토마토가 익은 토마토옆에 하루있으면 익는다. 모든 토마토가 익는데 걸리는 시간을 구하시오.

풀이

각 익은 토마토에서 안익은 토마토로 bfs를 진행하면 쉽게 풀 수 있다. 근데 토마토가 다 익었나 확인하는 O(n^2)함수에서 시간초과가 발생했다. 첨부터 끝까지 다 익었나 확인하는 방법 말고 익은 토마토의 개수를 계속 꾸준히 세서 전체 토마토와 같아지는지 확인하는 방법을 사용하자.

코드

from collections import deque


global n,m

m,n = map(int,input().split())

tomato = []

for _ in range(n):
	tomato.append(list(map(int,input().split())))

dx = [0,0,1,-1]
dy = [1,-1,0,0]

tomato_num = n*m

for i in range(n):
	for j in range(m):
		if tomato[i][j] == -1:
			tomato_num-=1
			

def bfs():
	global n,m
	count = 0
	q = deque([])
	for i in range(n):
		for j in range(m):
			if tomato[i][j] == 1:
				q.append((i,j,0))
				count += 1
				

	if count == tomato_num:
		return 0

	while q:
		y,x,time = q.popleft()
		for i in range(4):
			new_y = y+dy[i]
			new_x = x+dx[i]
			if 0<= new_y < n and 0 <= new_x < m and tomato[new_y][new_x] == 0:
				tomato[new_y][new_x] = 1
				count += 1
				q.append((new_y,new_x,time+1))
		if count == tomato_num:
			return time+1
	return -1

answer = bfs()

print(answer)