백준(baekjoon) 7576번: 토마토(골드 5, 파이썬 PYTHON) - 그래프와 순회

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

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

7576번: 토마토

 

import sys
from collections import deque

M,N=map(int,sys.stdin.readline().split())
tomato=[]
answer=[[0 for _ in range(M)]for _ in range(N)]
queue=deque()

for _ in range(N):
  tomato.append(list(map(int,sys.stdin.readline().split())))

for x in range(N):
  for y in range(M):
    if(tomato[x][y]==1):
      queue.append([x,y])

while queue:
  [row,col]=queue.popleft()
  if(row>0 and tomato[row-1][col]==0):
    tomato[row-1][col]=1
    answer[row-1][col]=answer[row][col]+1
    queue.append([row-1,col])
  if(row<N-1 and tomato[row+1][col]==0):
    tomato[row+1][col]=1
    answer[row+1][col]=answer[row][col]+1
    queue.append([row+1,col])
  if(col>0 and tomato[row][col-1]==0):
    tomato[row][col-1]=1
    answer[row][col-1]=answer[row][col]+1
    queue.append([row,col-1])
  if(col<M-1 and tomato[row][col+1]==0):
    tomato[row][col+1]=1
    answer[row][col+1]=answer[row][col]+1
    queue.append([row,col+1])

if any(0 in l for l in tomato):
  print(-1)
else:
  print(max(map(max,answer)))

 

※ 그래프와 순회

 

 

●  처음은 0일로 시작한다. 각 단계에서 익은 토마토를 접하여 그 인접한 토마토가 아직 안익었다면 이 단계에서 접한 익은 토마토가 익기까지 걸린 일 수에 1을 더한 값이 아직 익지 않은 인접한 토마토가 익기 까지 걸린 일 수가 된다. 그 후 인접한 익지 않은 토마토를 1로 표시하여 익었음을 표시해준다. 

 

● 모든 단계가 끝난 후, 토마토 칸에 아직 익지 않은 토마토가 있다면 -1을 출력해주고, 모두 익었다면 익기까지 가장 오래걸린 토마토가 익기까지 걸린 일 수를 출력해준다.