백준 토마토 코드 및 해설 (파이썬)
2021. 10. 4. 12:53ㆍalgorithm
반응형
https://www.acmicpc.net/problem/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)
반응형
'algorithm' 카테고리의 다른 글
백준 부분수열의 합 코드 및 해설 (파이썬) (0) | 2021.10.11 |
---|---|
백준 로봇 청소기 코드 및 해설 (파이썬) (0) | 2021.10.11 |
백준 설탕 배달 코드 및 해설 (파이썬) (0) | 2021.10.04 |
백준 별 찍기 코드 및 해설 (파이썬) (2) | 2021.09.29 |
백준 최종 순위 코드 및 해설 (파이썬) (0) | 2021.09.29 |