백준 7576(파이썬):토마토
백준 7576번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/7576
문제 내용
나의 풀이
import sys
from collections import deque
input=sys.stdin.readline
def bfs():
zero_count=0
queue=deque()
for i in range(n):
for j in range(m):
if box[i][j]==1:
queue.append((i,j,0))
if box[i][j]==0:
zero_count+=1
if zero_count==0:
return print(0)
temp_count=0
while queue:
x,y,day=queue.popleft()
for i in range(4):
rx,ry=x+dx[i],y+dy[i]
if 0<=rx<n and 0<=ry<m and box[rx][ry]==0:
box[rx][ry]=1
temp_count+=1
queue.append((rx,ry,day+1))
if zero_count==temp_count:
return print(day)
else:
return print(-1)
m,n=map(int,input().split())
box=[list(map(int,input().split())) for _ in range(n)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
bfs()
- 초기 익은 토마토들의 위치와 날짜를 큐에 넣어주고 익지 않은 토마토들의 개수를 세어준다.
- 이 때, 익지 않은 토마토가 없으면 0을 출력한다.
- 익지 않은 토마토가 존재하면 BFS로 익지 않은 토마토들을 익게 만들고 익은 토마토의 개수를 세어준다.
- 탐색이 종료되면 처음 익지않은 토마토들이 모두 익었으면 최소 날짜수를 출력하고, 그렇지 않으면 -1을 출력한다.
익지 않은 토마토의 수를 기준으로 조건을 나눠줬다…
풀이를 본 후
0의 개수(익지 않은 토마토의 개수)를 굳이 세지 않고 배열에 1씩 값을 더해가면서 최종적인 배열의 최대값-1로 최소 일수를 구해준다…
이 때, 최종 배열에 0이 있으면 -1을 출력한다. 또한, 어차피 0이 없을 때는 배열의 최대값은 1이기 때문에 0을 출력하는 상황도 해결된다…
그런데 내 풀이가 메모리와 시간이 조금더 좋게 나왔다…^^
해결한 후
항상 많은 상황을 생각하고 해결하도록 고민을 많이 하는것이 좋은것 같다.
