백준 - 7576번(BFS)

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

import sys
from collections import deque

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

arr = []
for i in range(m):
    arr.append(list(map(int,sys.stdin.readline().split())))

res = 0
q = deque()

for i in range(m):
    for j in range(n):
        if arr[i][j] == 1: #이미 익은 토마토가 시작지점
            q.append([i,j])
            #이미 익은 토마토가 1개 이상인 경우도 있으니 break 하면 안됨

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

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            #arr의 범위를 넘지않고 익지않은 토마토(0)과 만날때
            if 0<= nx < m and 0<= ny < n and arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] + 1
                q.append([nx,ny]) #q에 새로운 좌표 추가
BFS()

for i in range(len(arr)):
    for j in range(len(arr[i])):
        if arr[i][j] == 0: #익지않은 토마토가 존재할때
            print(-1)
            sys.exit() #프로그램 종료

        elif arr[i][j] > res:
            res = arr[i][j] #최대값 찾기

print(res-1) #시작하는 arr[i][j] 값이 1이기때문에 최종적으로 답에서 1빼주기

 

처음부터 익어 있던 토마토를 q에 담아준다. 여러 개일 가능성이 있다.

상, 하, 좌, 우 탐색을 해주면서 arr의 범위를 벗어나지 않고 익지 않은 토마토를 만날 경우

누적 횟수에 1을 더해주고 다시 q에 담아준다.

이를 BFS 탐색을 한다.

익지 않은 토마토가 탐색 후에도 존재할 경우 -1을 출력하고 프로그램 종료,

그렇지 않은 경우 최댓값을 찾아서 -1을 해준후 출력한다.