토마토 [백준 7576] - python

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

RIPE = 1
UN_RIPE = 0

def BOJ7576() :
  global M, N
  directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  def bfs(graph) :
    queue = deque()
    temp = [[-1 for _ in range(M)] for _ in range(N)]
    visited = [[False for _ in range(M)] for _ in range(N)]
    for i in range(N) :
      for j in range(M) :
        if graph[i][j] == 0 :
          continue

        temp[i][j] = 0
        if graph[i][j] == 1 :
          queue.append([i, j, 0])
          visited[i][j] = True
    
    while queue :
      curr_x, curr_y, curr_day = queue.popleft()

      n_day = curr_day + 1
      for dir_x, dir_y in directions :
        n_x = curr_x + dir_x
        n_y = curr_y + dir_y
        if 0 <= n_x < N and 0 <= n_y < M and graph[n_x][n_y] == 0 and visited[n_x][n_y] == False:
          visited[n_x][n_y] = True
          queue.append([n_x, n_y, n_day])
          temp[n_x][n_y] = n_day 
          graph[n_x][n_y] = 1
    return temp

  M, N = map(int, input().split())
  graph = []
  for _ in range(N) :
    graph.append(list(map(int, input().split())))
  
  temp_graph = bfs(graph)
  day = -1
  for i in range(N) :
    for j in range(M) :
      if temp_graph[i][j] == -1 :
        print(-1)
        return
      day = max(day, temp_graph[i][j])
  
  print(day)

BOJ7576()

 

접근 방법 : 

1. 그래프 탐색과 bfs를 이용해 하루가 지날때마다 토마토의 익는 과정을 코드로 구현해보고자 하였다.

2. 첫번째 시도는 while문 안에서 하루하루 더해주면서 토마토의 상자를 계속 업데이트 해주었지만 시간 초과가 발생하였다. 

3. 익는 것에 대한 그래프를 생성후 탐색 한번에 그래프를 업데이트 해주었다.

4. 아예 익지 못하는 상황에 대한 예외를 추가해 처리해 주었다.

 

장애물 이였던 것 : 

1. 시간을 하나씩 카운팅 하고 그래프를 업데이트 하는 방식으로 접근을 하였었더니 시간초과가 발생하였다. 
같은 함수를 매번 돌리는 것이 아닌 탐색 한번에 언제 전부 익는지를 가져오는 방법으로 변경하였다.

 

 

 

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

7576번: 토마토