[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-토마토 (BFS 활용)

 

 

지금까지 BFS 문제에서는 출발점을 격자판의 좌상단으로 해도 무리가 없었다면,

이 문제에서는 익은 토마토가 random한 위치에 주어지고, 익은 토마토를 기점으로 다른 토마토가 익는 상황이므로 

익은 토마토들의 위치를 queue에 먼저 쌓아줘야 한다.

 

 

import sys
from collections import deque
 
# sys.stdin=open('input', 'r')
sys.setrecursionlimit(10**6)    # 10**6 정도의 시간 limit을 주면 이걸 넘어가면 재귀를 끝낸다
                                # 백준사이트 같은 곳 가서 채점 받을 때 필요
if __name__=='__main__':
 
    n, m = map(int, input().split())
    tomato = [list(map(int, input().split())) for _ in range(m)]
    bfs_board = [[0]*n for _ in range(m)]       # 거리 값을 기록하기 위한 배열
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
 
    queue = deque()
    for i in range(m):
        for j in range(n):
            if tomato[i][j]==1:                 # 익은 토마토를 먼저 걸러내어
                queue.append((i, j))            # 그 좌표값을 큐에 쌓아준다
 
 
    res = 0                                     # res를 0으로 해주는 이유는, 모든 토마토가 이미 익어있는 상황이면
                                                # while문이 모두 돌아도 res의 값은 그대로일 것이기 때문에
                                                # 그대로 출력해주면 된다
    while queue:
        now = queue.popleft()
        for i in range(4):
            x = now[0]+dx[i]
            y = now[1]+dy[i]
            if 0 <= x < m and 0 <= y <n and tomato[x][y]==0:
                tomato[x][y]=1
                bfs_board[x][y]= bfs_board[now[0]][now[1]]+1
                if res < bfs_board[x][y]:
                    res=bfs_board[x][y]
                queue.append((x,y))
 
 
    flag = 0
    for i in range(m):
        for j in range(n):                      # 토마토 밭에 여전히 안익은 토마토(0)이 존재한다면
            if tomato[i][j] == 0:               # 토마토가 모두 익지는 못하는 상황이므로
                flag = 1                        # print(-1) 해주기 위해서 flag=1로 바꾼다
    if flag:
        print(-1)
    else:
        print(res)                              # res는 토마토가 이미 처음부터 모두 익은 상황인 0이 될 수도 있고,
                                                # BFS 돌고 나온 값이 나올 수도 있다.