백준 7576 토마토

유형 : bfs

풀이과정

1. ripen을 deque로 선언한 후, 토마토들의 정보를 읽으며 익은 토마토의 인덱스 (i,j)를 넣는다.

2. ripen에서 popleft로 하나씩 꺼내가며, 토마토의 이웃을 체크하고 익지 않은 토마토가 있으면 상태를 1로 바꾸어주고 ripen에 넣는다. 이때, time step을 세기위해, 각 time step마다, ripen에서 꺼내기 전에, ripen에 몇개의 요소가 들어있는지 체크해두고 popleft로 체크된 수 만큼만 빼고, 새로 넣는 토마토는 오른쪽으로 넣는다.

3. ripen이 빌때까지 2를 반복한 후, 장애물의 숫자와 익은 토마토의 숫자의 합이 m*m 일 경우에는 시간을, 아닐경우에는 -1을 반환한다.

 

Python Code

import collections
import sys
 
m,n = map(int,sys.stdin.readline().split())
row = 0
tomato = []
ripen=collections.deque()
obstacle_num =0
ripen_num=0
for i in range(n):
    temp = list(map(int,sys.stdin.readline().split()))
    for j in range(m):
        if temp[j]==1:
            ripen.append([row+1,j+1])
            ripen_num +=1
        elif temp[j] == -1:
            obstacle_num+=1
    temp.insert(0,-1)
    temp.append(-1)
    tomato.append(temp)
    row+=1
 
tomato.insert(0, [-1 for i in range(m+2)])
tomato.append([-1 for i in range(m+2)])
 
answer = -1
while len(ripen) != 0:
    answer+=1
    _num = len(ripen)
    for i in range(_num):
        t = ripen.popleft()
        #print(t)
        if tomato[t[0]+1][t[1]]==0:
            ripen.append([t[0]+1,t[1]])
            tomato[t[0]+1][t[1]]=1
            ripen_num+=1
        if tomato[t[0]-1][t[1]]==0:
            ripen.append([t[0]-1,t[1]])
            tomato[t[0]-1][t[1]]=1
            ripen_num+=1
        if tomato[t[0]][t[1]+1]==0:
            ripen.append([t[0],t[1]+1])
            tomato[t[0]][t[1]+1]=1
            ripen_num+=1
        if tomato[t[0]][t[1]-1]==0:
            ripen.append([t[0],t[1]-1])
            tomato[t[0]][t[1]-1]=1
            ripen_num+=1
if ripen_num+obstacle_num == n*m:
    print(answer)
else:
    print(-1)

* 편의를 위해서 tomato는 (m+2)*(m+2) 행렬로, 가장자리를 -1(장애물)로 채웠습니다.

 

문제풀기

7576번: 토마토