[Baekjoon] 7576 - 토마토 BFS (Python)

[Baekjoon] 7576 - 토마토 (BFS)

---

🧐 문제 설명

---

😍 나의 풀이

[Baekjoon] 2178 - 미로 탐색 (BFS) 이 문제하고 거의 똑같다. '미로 탐색' 문제는 출발 지점이 하나로 정해지고 도착 지점도 정해지지만, '토마토' 문제는 출발 지점이 여러 개일 수 있고, 도착 지점은 없이 더 이상 방문할 수 있는 곳이 없을 때 탐색을 종료한다.

출발 지점이 여러개인 문제
1이 여러 군데에서 탐색을 시작할 수 있기 때문에 graph를 전체 탐색하여 요소가 1인 인덱스들을 시작 큐에 집어넣고 탐색을 시작한다.

이 후, 큐의 크기만큼 반복문을 돌려서(그래야 모든 시작 지점이 탐색 시작)을 상하좌우 한 칸씩 탐색하고 0이면 그 노드를 큐에 다시 삽입한다. 기존 큐에 있는 인덱스들(시작지점)을 모두 탐색하고나면 반복문을 빠져나와 count를 +1 한다.

더이상 큐의 반복을 수행할 수 없을 때(모든 가능한 지점 탐색 완료), 무한 루프를 break 한다.

벽으로는 이동 못하는 문제
graph의 요소가 -1일 때는 '벽'이기 때문에 그 방향으로는 방문할 수 없지만 어차피 상하좌우 이동 시, 값이 0일 때만 방문하면 되기 때문에 그렇게 처리한다.

from collections import deque

M, N = map(int, input().split())

graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

queue = deque()
for i in range(N):  # 큐에 시작 정점 할당
    for j in range(M):
        if graph[i][j] == 1:
            queue.append([i, j])

def bfs():
    dx = [-1, 1, 0, 0]  # 좌우
    dy = [0, 0, -1, 1]  # 상하
    count = -1

    while queue:
        count += 1
        for i in range(len(queue)):
            y, x = queue.popleft()

            for j in range(4):
                nx = x + dx[j]
                ny = y + dy[j]

                if 0<=nx<M and 0<=ny<N:
                    if graph[ny][nx] == 0:
                        queue.append([ny, nx])
                        graph[ny][nx] = graph[y][x] + 1

    for i in graph:
        if 0 in i:	# 모두 탐색 못 한 경우 check
            return -1
    return count

print(bfs())