백준 7576번 토마토 | python | bfs

문제

링크

풀이

아주 베이직한 bfs 문제이다. 왜 골드이지 싶은..?

먼저 익은 토마토가 존재하는 배열의 인덱스 좌표값을 큐에 모두 삽입한 후,
이들을 하나씩 popleft()하면서 상하좌우에 있는 값에 (자신의 값+1)을 더해주며 업데이트 하면 된다.

값이 -1인 경우는 토마토가 들어있지 않은 칸이다. 따라서 bfs()를 수행할 때 0이 아닌 값들에 대해서만 큐의 삽입 조건으로 본다. (0이 아니라는 뜻은 이미 익은 토마토이거나 토마토가 들어있지 않은 칸이므로)

전체 코드는 아래와 같다.

# from collections import deque
# import sys

# input = sys.stdin.readline


# m, n = map(int, input().strip().split())
# arr = []
# visited = [[0] * m for _ in range(n)]
# for _ in range(n):
#     arr.append(list(map(int, input().strip().split())))
# d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# q = deque()
# for y in range(n):
#     for x in range(m):
#         if arr[y][x] == 1:
#             q.append((y, x))
#             visited[y][x] = 1
#         elif arr[y][x] == -1:
#             visited[y][x] = 1

# while q:
#     y, x = q.popleft()
#     for dy, dx in d:
#         Y = dy + y
#         X = dx + x
#         if 0 <= Y < n and 0 <= X < m and not visited[Y][X]:
#             arr[Y][X] = arr[y][x] + 1
#             visited[Y][X] = 1
#             q.append((Y, X))


# max = -2
# for y in range(n):
#     for x in range(m):
#         if arr[y][x] == 0:
#             print(-1)
#             exit()
#         else:
#             if max < arr[y][x]:
#                 max = arr[y][x]
# print(max - 1)

from collections import deque
import sys

input = sys.stdin.readline


m, n = map(int, input().strip().split())
arr = []
# visited = [[0] * m for _ in range(n)]
for _ in range(n):
    arr.append(list(map(int, input().strip().split())))
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
for y in range(n):
    for x in range(m):
        if arr[y][x] == 1:
            q.append((y, x))
            # visited[y][x] = 1
        elif arr[y][x] == -1:
            pass
            # visited[y][x] = 1

while q:
    y, x = q.popleft()
    for dy, dx in d:
        Y = dy + y
        X = dx + x
        if 0 <= Y < n and 0 <= X < m and not arr[Y][X]:
            arr[Y][X] = arr[y][x] + 1
            q.append((Y, X))

max = -2
for y in range(n):
    for x in range(m):
        if arr[y][x] == 0:
            print(-1)
            exit()
        else:
            if max < arr[y][x]:
                max = arr[y][x]
print(max - 1)