❓ Problem

🤔 How

다음과 같은 조건을 알수있다.

1. 토마토가 모두 익을 경우 토마토가 모두 익는데 걸리는 최소 시간을 출력해야한다.
2. 만약 토마토가 익지 않는 경우가 있을때는 -1 을 출력해야한다.
3. 토마토가 비어있는 지역이 있다 (board 에 -1로 표시)

토마토가 모두 익는데 걸리는 '최소' 시간 가져와야하므로 bfs풀이가 적합 하다고 판단하였다.
bfs 로직으로 각 depth 를 board에 표기하고 depth 의 최대값이 갱신될 경우 모두익는데 최소 걸리는 시간이라고 판단했다.

bfs 순회로직을 모두 끝낸이후 익지 않은 토마토가 있는지 검사하고 이경우 -1 을 반환하도록 작성하였다.

❗ Solve

@@ -0,0 +1,51 @@
# 토마토
import sys
from collections import deque
input = sys.stdin.readline

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

N, M = map(int, input().split())
visited = [[False for _ in range(N)] for _ in range(M)]
board = []
for _ in range(M):
    board.append(list(map(int, input().split())))


def find_tomato(board, visited): # 초기 토마토 검사
    li = []
    for y in range(M):
        for x in range(N):
            if board[y][x] == 1:
                visited[y][x] = True
                li.append([x, y, 0])
            elif board[y][x] == -1: # 가지 못하는 곳일 경우 미리 방문처리함으로서 방문하지 않도록 
                visited[y][x] = True
    return li


def bfs(board, visited): # bfs 최소 익는 시간 검사
    preset_tomato = find_tomato(board, visited)
    q = deque(preset_tomato)
    answer = 0
    while q:
        x, y, depth = q.popleft() #depth 현재까지 익는 시간 표기
        if depth > answer: #최대 시간 갱신시 답 변경
            answer = depth 
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[ny][nx]:
                visited[ny][nx] = True
                board[ny][nx] = 1
                q.append([nx, ny, depth+1])

    for y in range(M): # 익지않은  토마토가 있는지 검사
        if 0 in board[y]:
            return -1

    return answer


print(bfs(board, visited))