📚 7576 - 토마토

토마토

문제에 대한 이해

최단 거리 구하는 문제에서는 bfs를 사용한다!
bfs의 대표적인 문제에서 몇 가지 추가된 점들이 있다.

• 시작하기에 앞서 그래프에서 익은 토마토가 어디인지 먼저 위치를 찾고 저장해야 한다. (따로 할시, 원하는 결과를 얻을 수 없다. 더 빨리 토마토를 익을 수 있는데 다른 결과가 저장됨)
• 여러 곳에서 시작하여 공통으로 지나가는 점이 있다면 최소 값을 구해야한다. (bfs에 시작 점들을 저장해놓고 돌리면 최소 값을 구할 수 있다.)
• 끝에서 그래프 전체를 검토하여 지나가지 못한 위치가 있는지 확인해야 한다.

➡️ 소스를 보면 쉽게 이해가 될 것이라 생각한다.

소스

# 이와 같이 시작점이 정해진 그래프에서는 dfs를 사용하며, 미리 해당 점들을 저장해놓기

import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split())
graph = []

queue = deque()

x_coordinate = [-1, 0, 1, 0]
y_coordinate = [0, 1, 0, -1]

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


def bfs():
    while queue:
        cur_x, cur_y = queue.popleft()

        for i in range(4):
            next_x = cur_x + x_coordinate[i]
            next_y = cur_y + y_coordinate[i]

            if (0 <= next_x < n) and (0 <= next_y < m) and (graph[next_x][next_y] == 0):
                graph[next_x][next_y] = graph[cur_x][cur_y] + 1
                queue.append((next_x, next_y))


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


bfs()

result = -2
isTrue = False

for i in graph:
    for arr_data in i:
        if arr_data == 0:
            isTrue = True

        result = max(result, arr_data)


if isTrue:
    print(-1)
else:
    print(result - 1)

채점 결과

참고

• https://pacific-ocean.tistory.com/267