[Algorithm] 백준 BOJ 7576 토마토 python 파이썬 BFS 골드 5 / 메모리 초과

Private 난이도 : ♥♥♥♥♡

7576번: 토마토

import sys
from collections import deque
sys.setrecursionlimit(10**6)

n, m= map(int,input().split(' '))
graph=[]
for mm in range(m):
    graph.append(list(map(int, input().split(' '))))

full_count=0 # 총 0의 갯수 = 익어야하는 토마토 갯수
ripe=deque()
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0 :
            full_count+=1
        if graph[i][j]==1:
            ripe.append([i,j])

x=[1,0,-1,0]
y=[0,-1,0,1]

def bfs(graph,ripe,days,count):
    while True :
        next_ripe=deque() # per day
        while ripe:
            now = ripe.popleft()
            i=now[0]
            j=now[1]
            for direction in range(len(x)):
                if i+y[direction] >=0 and i+y[direction]< m and j+x[direction] >=0 and j+x[direction]<n:
                    if graph[i+y[direction]][j+x[direction]] ==0:
                        graph[i+y[direction]][j+x[direction]]=1
                        count+=1
                        next_ripe.append([i+y[direction], j+x[direction]])

        if not next_ripe:
            break
        days +=1
        ripe=next_ripe
    return days,count

days, count = bfs(graph,ripe,0,0)

if full_count == count:
    print(days)
else : 
    print(-1)

설명

• 처음에 0이었던 모든 토마토를 ripe라는 큐에 넣고 시작한다.
• next_ripe에 이번에 익게 된 토마토(인접 토마토)를 넣고 다음 날에 그 토마토들로부터 전파시킨다.

배운 점

• 원래 썼던 코드는 메모리초과가 있었다.
  

  import sys
  from collections import deque
  sys.setrecursionlimit(10**6)
  
  n, m= map(int,input().split(' '))
  
  graph=[]
  for mm in range(m):
      graph.append(list(map(int, input().split(' '))))
  
  full_count=0 # 총 0의 갯수 = 익어야하는 토마토 갯수
  ripe=deque()
  for i in range(m):
      for j in range(n):
          if graph[i][j] == 0 :
              full_count+=1
          if graph[i][j]==1:
              ripe.append([i,j])
  
  x=[1,0,-1,0]
  y=[0,-1,0,1]
  
  def bfs(ripe,days,count):
  
      next_ripe=deque() # per day
      while ripe:
          now = ripe.popleft()
          i=now[0]
          j=now[1]
          for direction in range(len(x)):
              if i+y[direction] >=0 and i+y[direction]< m and j+x[direction] >=0 and j+x[direction]<n:
                  if graph[i+y[direction]][j+x[direction]] ==0:
                      graph[i+y[direction]][j+x[direction]]=1
                      count+=1
                      next_ripe.append([i+y[direction], j+x[direction]])
  
      if not next_ripe:
          return days, count
  
      days +=1
      return bfs(next_ripe,days,count)
  
  days, count = bfs(ripe,0,0)
  
  if full_count == count:
      print(days)
  else : 
      print(-1)

• 전역변수, 지역변수
  graph라는 변수가 bfs라는 함수 안에서 바뀌지 않기 때문에 graph를 파라미터로 넣지 않고도 사용할 수 있었다. 그래서 뺐다. 함수 내에서 변경되지 않으면 global을 사용하지 않고 전역변수로 사용된다는 것을 알게 되었다. 이 블로그를 참고했다.
• tail recursion optimize
  메모리 초과의 핵심 원인이었다. 머릿속으로는 이것 때문일것이라고 생각했었는데 정말이었다. 다음 참고 블로그가 더 설명이 잘 되어 있지만 간단히 설명하자면, return 값이 다음 불러지는 함수가 끝날 때까지 받을 수 없는 상황이 이어져서 결국에 모든 bfs의 재귀 함수가 닫히지 않는 상태로 존재해서 메모리 초과가 일어나는 것이다. 그래서 이 상황을 해결하는 방법이 tail recursion optimize이다. 근데 python에서는 pip로 설치해서 해결해야하기 때문에 원인은 알았지만 해결할 수는 없었다. 그래서 밑의 방법이 문제의 해결방법이다.
• 입력크기와 재귀
  이 블로그를 통해 입력 배열이 500x500이면 재귀를 사용할 때 그냥 메모리 초과가 일어나는 크기라는 것을 알게 되었다. 그래서 재귀를 쓰지 않는 것이 맞다.
• BFS를 두 번째로 풀어본 문제였는데, DFS만 하다보니 큐와 재귀가 중복으로 사용된 것 같다. for이나 while을 통해서 재귀를 없애야겠다.

재시도

2년이 지나 2024년 2월 3일 BFS 감을 다시 찾기 위해

정석적인 문제를 찾다가 다시 풀어보고 싶어졌다.

왜냐하면 위의 코드가 BFS를 처음 시작할 때 짰던 코드라서 이제 보니 하나도 마음에 들지 않았기 때문이다.

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

m,n = map(int,input().strip().split(' '))
graph=list()
for i in range(n):
    graph.append(list(map(int,input().strip().split(' '))))

ripe=list()
normal_tomato=n*m
for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            ripe.append([i,j,0])
            normal_tomato-=1
        elif graph[i][j]==-1:
            normal_tomato-=1

def bfs(ripe, graph, normal_tomato):
    q=deque(ripe)
    di=[[1,0,-1,0],[0,1,0,-1]]
    day=0
    while q:
        x,y,day=q.popleft()
        
        for i in range(4):
            dx=x+di[0][i]
            dy=y+di[1][i]
            
            if 0<=dx and dx<n and 0<=dy and dy<m and graph[dx][dy]==0:
                graph[dx][dy]=1
                normal_tomato-=1
                q.append([dx,dy,day+1])
    return day, normal_tomato

bfs_day, nt=bfs(ripe, graph, normal_tomato)

if nt>0:
    print(-1)
else:
    print(bfs_day)

 

마지막 처리만 조금 깔끔하지고 생각하는 방식은 비슷한 것 같다.