[백준/파이썬] 7576번: 토마토

문제

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

풀이

• M$\times$N 사이즈 토마토 상자
• 토마토 보관 후, 하루마다 익은 토마토 주위 토마토(상하좌우)가 익음
• 토마토가 모두 익는 최소 일수
• 1: 익은 토마토, 0: 익지 않은 토마토, -1: 빈 칸

토마토가 모두 익는 최소 일수를 구하는 문제 = BFS

토마토를 먼저 상자에 담아줍니다.

box = []
queue = deque()
for i in range(m):
    row = list(map(int,input().split()))
    box.append(row)

담아줄 때, 익은 토마토(1)가 있는 좌표를 모두 queue에 담아줍니다.

    for j in range(n):
		if row[j] == 1:
        	queue.append((i,j))

이제 저장된 좌표를 갖고 탐색을 시작

def bfs():
	# 상하좌우
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    while queue:
        x,y = queue.popleft() # 탐색을 진행할 좌표
        
        # 상하좌우 탐색
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0 <= nx < m and 0 <= ny < n and box[nx][ny] == 0: # 범위 내 && 익지 않은 토마토일 때
                queue.append((nx,ny)) # queue에 추가
                box[nx][ny] = box[x][y] + 1 # 이전 값 +1

모든 토마토가 익게 됐을 때 최대값만 추출하면 되므로 값을 계속 증가시켜 줍니다.

탐색을 마친 후 최대값을 출력해줍니다.
문제에서 모든 과일이 익지 않았을 경우(0이 존재할 경우) -1을 출력하라고 했으니 유의하세요 🥲

res = 0
for r in box:
	if 0 in r: # 익지 않은 토마토가 있을 경우
    	print(-1)
        exit() # 종료
	res = max(res, max(r)) # 최대값 갱신
print(res-1)

처음 입력 받을 때 익은 과일을 1로 선언하고 이 값을 증가시켜 결과를 도출해냈으므로 res에서 1을 빼주어야 값이 올바르게 나옵니다. ☺️

코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

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

if __name__ == "__main__":
    n,m = map(int,input().split())
    
    box = []
    queue = deque()
    for i in range(m):
        row = list(map(int,input().split()))
        box.append(row)
        for j in range(n):
            if row[j] == 1:
                queue.append((i,j))
    
    bfs()

    res = 0
    for r in box:
        if 0 in r:
            print(-1)
            exit()
        res = max(res, max(r))
    print(res-1)