골드 V

💡문제 분석 요약

BFS

💡알고리즘 설계

모든 토마토를 보고 안익었으면 zero+=1, 상자면 box+=1로 값을 파악한다.

만약 안익은 토마토가 없다면 0을 출력한다.

익은 토마토를 찾은 뒤, queue에 익은 여부와 값, 날짜를 넣어준다.

queue에 값이 없을때 까지 왼쪽부터 꺼낸다.

상자가 아닌 경우 (not -1) 앞뒤왼오의 값을 1로 만들고 queue에 넣는다.

익은 값과 상자를 모두 더해 n*m이 나오면 day-1을 출력하고 아닌경우 -1을 출력한다.

💡코드

pypy3으로 제출. python3 시간초과

from collections import deque
m,n= map(int,input().strip().split())
tomato = []
ripen =0
box = 0
day =0
zero =0
dx =[0,0,-1,1]
dy = [1,-1,0,0]
for _ in range(n):
    tomato.append(list(map(int, input().strip().split())))
visited = [[False for _ in range(m)]for _ in range(n)]
queue = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] ==1:
            queue.append([tomato[i][j],i,j,day])
        elif tomato[i][j]==-1:
            box +=1
        elif tomato[i][j] == 0:
            zero +=1
if zero>0:
    while queue:
        value, i,j,day=queue.popleft()
        if not visited[i][j] and value ==1:
            visited[i][j] = True
            ripen+=1
            for z in range(4):
                x = dx[z]+i
                y = dy[z]+j
                if 0<=x<n and 0<=y<m:

                    if tomato[x][y]!=-1:
                        tomato[x][y]=1
                        queue.append([tomato[x][y],x,y,day+1])
    if box+ripen == n*m:
        print(day-1)
    else:
        print(-1)
else:
    print(0)

💡시간복잡도

N

💡다른 사람의 코드

  • box을 세지 않고 안 익은 토마토를 센다. 굳이 visited로 관리하지 않고 어차피 0이면 1로 바꾸고 append하니까 상관없으며 익지 않은 토마토의 값으로 -1을 출력한다.
  • tomato에 값이 들어있으므로 굳이 값을 queue에 넣지 않고 (i,j)의 값을 넣는다.
  • while queue 선언 후 새로운 new_queue를 선언. 익은 토마토의 주위를 둘러볼 때, 익지 않은 토마토면 안익은 토마토의 값을 하나씩 줄인다. 그리고 토마토를 익게 만든다. 다음날 영향을 미치는 토마토를 new_queue에 넣고, queue = new_queue 로 교체한다. 교체후 day+=1

💡 기억할 것

visited를 써야하는 이유는 append의 조건이 성립될 때의 값이 유지될 때이다. 따라서 값에 0인 경우 append를 하는 조건이면, 1로 바꿔준뒤 넣으면 다시 중복으로 넣지 못한다.

또한, 여기서 토마토 1이 중복해서 들어가는 거 아닐까 걱정했는데, 애초부터 처음 돌 때 모든 익은 토마토의 값을 넣었으므로 중복할리 없다.