[파이썬]백준 7576 토마토

링크

백준 7576 토마토

bfs를 구현해서 풀었다.
가장 고민했던 부분은 익은토마토(1)가 여러개가 있을 경우 한쪽에서만 시작하는게 아니라 모든 곳에서 동시에 퍼져나가게 구현해야 한다는 점이었다.
해당 고민은 1을 입력받을 때 탐색해 큐에 미리 담아놓고 해당 큐로 bfs를 돌리는 방법으로 해결했다.
bfs를 돌린 후 box안에 0이 있는지 검사하기 위해 check라는 함수를 만들었는데 괜히 안써도 되는 반복문을 쓴것같다. bfs함수 안에서 해당 부분을 해결할 수 있는 방법을 고민해봐야겠다.

정답 코드

import sys
from collections import deque

def bfs(q):
    global maxd
    dr = [-1, 0 , 1 ,0]
    dc = [0, 1, 0, -1]

    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M and box[nr][nc] == 0:
                box[nr][nc] = 1
                distance[nr][nc] = distance[r][c] + 1
                q.append([nr, nc])

                if distance[nr][nc] > maxd:
                    maxd = distance[nr][nc]

def check(arr):
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0:
                return -1


M, N = map(int, sys.stdin.readline().split())
box = []
q = deque()
distance = [([0] * M) for _ in range(N)]
maxd = 0

for i in range(N):
    tmp = list(map(int, sys.stdin.readline().split()))
    for j in range(M):
        if tmp[j] == 1:
            q.append([i, j]) #익은 토마토가 있는 곳을 큐에다가 담아서 큐 채로 bfs에 넘겨줌
    box.append(tmp)

bfs(q)
if check(box) == -1:
    print(-1)
else:
    print(maxd)

알게된 것👨‍💻

• 여러곳에서 bfs탐색을 하고싶으면 시작점을 미리 큐에담아놓고 bfs를 돌린다.