백준 토마토 코드 및 해설 (파이썬)

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

7576번: 토마토

 

요즘 비슷한 문제를 엄청 많이 풀었다. 다 거기서 거기네.. bfs...

비슷한 bfs 문제들 

• 경쟁적 전염
• 연구소
• 감시 피하기
• 인구 이동

 

make_ripe 함수로 하루동안 토마토의 변화를 계산한다. 우선 익은 토마토가 있는 좌표들인 tomato를 큐로 만들고, 이들을 하나씩 pop하면서 그 토마토의 인접한 부분 중에 0인 곳이 있으면 1로 바꿔준다. 그리고 이제 익게 되었으니 다음 날엔 이들도 인접한 토마토를 익게 만들 수 있다. 따라서 이 좌표를 new_tomato에 추가해준다. 또한 ripen을 1씩 증가해준다. 

인접한 곳을 익게 만들 수 있는 토마토가 남아있는 한 계속 이 함수를 실행한다. 실행이 끝난 후 처음에 익지 않았던 토마토의 개수인 unripes와 함수 실행 결과 익게 된 토마토의 개수인 ripen이 같다면 모든 토마토가 익게 된 것이다. 이땐 days를 출력해준다. 그렇지 않은 경우 아무리 오래 지나도 모든 토마토가 익을 수는 없으므로 -1을 출력한다.

 

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().split())

storage = [] # 전체 창고 
tomatos = [] # 익은 토마토의 좌표
unripes = 0 # 익지 않은 토마토의 개수 
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    storage.append(row)
    for j in range(M):
        if row[j] == 1:
            tomatos.append((i,j))
        elif row[j] == 0:
            unripes += 1

dx = [-1,1,0,0]
dy = [0,0,-1,1]

# 하루동안 토마토 창고 안에서의 변화
def make_ripe(storage, M, N, tomatos, ripen):
    tomatos = deque(tomatos)
    # 새로 익은 토마토의 좌표 
    new_tomatos = []
    # 각 토마토의 인접한 부분에 0이 있다면 1로 수정하기 
    while tomatos:
        a,b = tomatos.popleft()
        for x,y in zip(dx,dy):
            adj_x, adj_y = a+x, b+y
            if adj_x in range(N) and adj_y in range(M):
                if storage[adj_x][adj_y] == 0:
                    storage[adj_x][adj_y] = 1 # 익게 만들기
                    ripen += 1 
                    new_tomatos.append((adj_x, adj_y))
    return storage, new_tomatos, ripen

days = -1
# 익지 않았다가 익게 된 토마토의 개수 
ripen = 0
while tomatos:
    storage, tomatos, ripen = make_ripe(storage, M, N, tomatos, ripen)
    days += 1

# 처음에 익지 않은 토마토의 개수와 익게 된 토마토의 개수가 같다면 모두 익은 것이므로 days를 출력하지만, 그렇지 않은 경우 아무리 오랜 시간이 지나도 토마토가 익지 못하므로 -1을 출력함
print(days) if unripes == ripen else print(-1)