[백준_7576] 토마토 python

오늘 배운 점 : bfs 동시에 돌릴 수 있다. (좌표를 다 큐에 때려놓고 시작하면 된다.)

# m, n 입력
m, n = map(int, input().split())

# storage
storage = [
    list(map(int, input().split()))
    for _ in range(n)
]

# in_range(x, y):
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# can_go(x, y)
def can_go(x, y):
    # 범위 내에 없으면
    if not in_range(x, y):
        # 실패
        return False
    # 빈칸이면
    if storage[x][y] == -1:
        # 실패
        return False
    # 방문한 칸이면
    if visited[x][y] == 1:
        # 실패
        return False
    # 이외에는 성공
    return True

# bfs()
def bfs():
    while q:
        # 언팩킹
        x, y = q.popleft()

        # dxs, dys 상 하 좌 우 순서 상관 x
        dxs, dys = [-1, 1, 0, 0], [0, 0, 1, -1]
        for dx, dy in zip(dxs, dys):
            # 다음 조사 위치
            nx, ny = x + dx, y + dy
            # 갈 수 있으면,
            if can_go(nx, ny):
                # 방문표시 해주고,
                visited[nx][ny] = 1
                # 큐에 넣어주고,
                q.append((nx, ny))
                # step 배열 관리
                step[nx][ny] = step[x][y] + 1

# all_tomato()
def all_tomato():
    for i in range(n):
        for j in range(m):
            if storage[i][j] == 0:
                return False
    return True

# blocked()
def blocked():
    for i in range(n):
        for j in range(m):
            # 저장고의 값이 0이고 step의 값이 0이면,
            if storage[i][j] == 0 and step[i][j] == 0:
                # 막힌것임
                return True
    return False

# 설계

# visited (방문 기록을 해 줄 배열)
visited = [
    [0] * m
    for _ in range(n)
]

# step (시간을 기록 해 줄 배열)
step = [
    [0] * m
    for _ in range(n)
]

# 큐 사용 준비
from collections import deque

# 큐
q = deque()

# tomato_pos
tomato_pos = []

# storage를 돌면서
for i in range(n):
    for j in range(m):
        # 토마토를 만나면
        if storage[i][j] == 1:
            # 위치 기록
            tomato_pos.append((i, j))

# 익은 토마토들의 위치들을 모두 큐에 넣어주기
for tomato in tomato_pos:
    # 언팩킹
    x, y = tomato
    # 방문 처리
    visited[x][y] = 1
    # 큐에 넣어주고
    q.append((x, y))
# bfs 돌려주기
bfs()

# 모든 토마토가 익어있는 상태일 경우
if all_tomato():
    # 0 출력
    print(0)

# 토마토가 모두 익지 못하는 상황이면
elif blocked():
    # -1 출력
    print(-1)

# 이외의 상황 즉, 일반적인 상황
else:
    # 정답용
    ans = 0

    # step 돌면서
    for i in range(n):
        for j in range(m):
            # 최댓값을 찾으면
            if step[i][j] > ans:
                # 최댓값 갱신
                ans = step[i][j]
    # 출력
    print(ans)