골드5 토마토(7576)

7576번: 토마토

최소라는 단어를 보고 바로 BFS를 사용한다는 것을 알았다. 그렇게 처음에는 BFS를 활용해서 풀었는데 생각해보니 한 곳에서 시작한 첫 포인트가 토마토 전체를 익은 상태로 만들어 더 많은 일 수가 나왔다.

시작점이 동시에 출발해야하는 것을 깨닫고, 이번 알고리즘2 수업에서 들은 Multi Source BFS를 떠올려서 queue에 시작점을 넣어 탐색하게 만들었다. 그렇게 푸니 최소 일수가 나온것이다.

import sys
from collections import deque
input = sys.stdin.readline

directions = [(-1, 0),(0, -1),(1, 0),(0, 1)]

def bfs(startPoints):
  q = deque()
  for p in startPoints:
    q.append(p)
    visited[p[0]][p[1]] = True
  while q:
    start = q.popleft()
    for d in directions:
      nextX = start[0] + d[0]
      nextY = start[1] + d[1]
      if (0<=nextX<n and 0<=nextY<m) and matrix[nextX][nextY] == 0:
        q.append((nextX, nextY))
        matrix[nextX][nextY] = matrix[start[0]][start[1]] +  1
        visited[nextX][nextY] = True

m, n = map(int, input().split())
visited = [[False]*m for _ in range(n)]
matrix = [list(map(int, input().split())) for _ in range(n)]
multiSource = [(i, j) for i in range(n) for j in range(m) if not visited[i][j] and matrix[i][j] == 1]

bfs(multiSource)

result = 0
for i in matrix:
  if 0 in i:
    print(-1)
    break
  result = max(max(i), result)
else: print(result-1)