7576번 토마토

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

---

아이디어

먼저 토마토를 입력 받고 익은 토마토들만 큐에 넣은 후 bfs를 돌렸다. bfs 후 토마토의 결과에 0이 하나라도 있으면 하나라도 안 익은 상황이므로 -1을 출력하고 즉시 종료한다.

만약 그게 아니라면 익는 날짜를 출력해야하는데 bfs에서 돌 때 1인 곳 기준으로 상하좌우에 0인 토마토가 있으면 2로 만들어주었다. 이렇게 시작을 1인 토마토에서 했으므로 마지막 결과에서 -1을 해주어야한다.

2차원 리스트에서 최댓값 찾는 방법은 다음과 같이 하면 된다.

print( max(map(max, listname)) )

---

코드

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

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 > nx or nx >= n or 0 > ny or ny >= m: continue
            if tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[x][y] + 1
                queue.append([nx, ny])
    return


m, n = map(int, input().split())
# 익으면 1, 익지 않으면 0, 없는 건 -1
tomato = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우(순서무관)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 익은 토마토들 큐에 넣기
queue = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            queue.append([i, j])
bfs()
# 0이 있으면 익지 못하는 상황이므로 -1 출력
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            print(-1)
            exit(0) # 즉시 종료

print( max(map(max, tomato)) - 1)