[백준] 7576번(토마토)

백준 7576번

최종 제출 코드

import sys
from collections import deque

input = sys.stdin.readline

m,n = map(int, input().split())
array = []
queue = deque()

for i in range(n):
  row = list(map(int, input().split()))
  for j in range(m):
    if row[j] == 1:
      queue.append([j,i])
  array.append(row)
  
dx = [-1,1,0,0]
dy = [0,0,-1,1]

while queue:

  x,y = queue.popleft()
  
  for i in range(len(dx)):
    if x+dx[i] <0 or x+dx[i] >= m or y+dy[i] <0 or y+dy[i] >= n:
      continue

    if array[y+dy[i]][x+dx[i]] == 0:
      array[y+dy[i]][x+dx[i]] = array[y][x]+1
      queue.append([x+dx[i],y+dy[i]])

result = 0

for i in range(n):
  if array[i].count(0) > 0:
    result = 0
    break
  result = max(result, max(array[i]))

print(result-1)

◼️ 미로 탐색 문제와 비슷한 논리

• 차이점은 미로 탐색 문제는 시작 노드가 항상 동일하게 [0, 0]이나, 이 문제에서는 시작 노드가 여러개일 수 있으며 그 위치를 탐색해서 저장해줘야 한다.
• 또한 마지막 결과 출력시 익지 않은 토마토(배열값이 0)가 있는지 판별한 후, array 배열 내의 최대값을 이용하여 모든 토마토가 익을 때까지 걸리는 시간을 출력해야 한다.

◼️ 시간초과

• 처음에는 queue의 자료구조로 deque가 아닌 list를 이용
• 코드 구현 상에서는 더 이상 실행시간을 줄일 수 있는 부분이 없는 것 같은데 계속해서 시간초과가 떠서 오답
• 검색해보니 list가 아닌 deque 이용하면 실행시간을 줄일 수 있음

◼️ WHY❓

• 이 문제에서 queue에 대해 사용하는 연산은 append()와 pop(0) or popleft() 뿐이다.
• append()의 경우 list와 deque에서의 연산시간이 동일함
• 하지만 list에서 pop(0)의 경우 O(n)의 시간이 걸리는 반면, deque에서는 popleft()의 연산이 O(1)의 시간만을 소요
  ⇒ list를 사용하면 노드의 개수가 늘어날 수록 pop(0) 연산에 많은 시간 소요
  ⇒ deque 자료구조를 사용하는 것이 더 효율적

deque 자료