[BOJ_7576] 토마토

토마토가 존재하는 곳으로부터 상하좌우로 하루에 한 칸씩 익어나가는데 며칠이 걸리는 것인지 구하는 문제입니다. 기본적으로 지난번에 풀어본 "미로탐색(BOJ_2178)" 문제와 비슷합니다. 하지만 추가로 생각해야 할 문제가 있었는데 여러 곳에서 토마토가 익어 나갈 수 있다는 점(미로 탐색 문제와 다르게 한 시작점에서 탐색을 해나가지 않는다)입니다.

그래서 토마토 밭에서 1인 곳을 찾아서 큐에다 다 넣어주고 너비탐색을 한 후(미로탐색과 동일하게 1씩 증가시킵니다)

너비탐색이 끝났는데 0인 경우는 -1을 출력하고

얼마나 걸리는 지 구할 때는 단순히 토마토 밭에서 최댓값을 구하면 됩니다.

if days < tomatoes[i][j]:
  days = tomatoes[i][j]

파이썬 삼항 연산자(Ternary operators) 문법

print("True는 참" if True else "True는 거짓")

print(days-1 if flag else -1)

이렇게 하면 -1의 결과를 받아볼 수 있겠죠

 

from collections import deque

m, n = map(int, input().split())
tomatoes = []
for _ in range(n):
	tomatoes.append(list(map(int,input().split())))

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

queue = deque()
for i in range(n):
	for j in range(m):
		if tomatoes[i][j] == 1:
			queue.append((i,j))
bfs()
for i in range(n):
	for j in range(m):
		if tomatoes[i][j] == 0:
			flag = False
		if days < tomatoes[i][j]:
			days = tomatoes[i][j]
            
print(days-1 if flag else -1)
		

 

www.acmicpc.net/problem/7576

7576번: 토마토