[백준]7576번: 토마토

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

7576번: 토마토

---

하다가 잘 안 돼서 다른 분들 코드 참고해서 수정했다..

나는 언제쯤 혼자서 빠르게 풀 수 있을까?ㅠㅡㅠㅜ

 

아이디어

1. 처음부터 익어 있는 토마토 좌표를 큐에 저장하고 bfs를 수행한다
2. 인접한 칸 중에서 아직 안 익은 토마토가 있으면 (인접한 좌표의 그래프 값)을 (현재그래프값+1) 로 바꾸어준다
3. bfs가 종료되면 여전히 안 익은 토마토가 있는지 검사하고 결과를 출력한다.

• 익지 않은 토마토가 존재한다면 1을 빼준다.
• 토마토가 모두 익었다면 그래프값중 가장 큰 값이 소요 일수이다. (소요 일수는 2부터 카운트했으니 1을 빼고 출력해준다.)

 

 -예시)

 

초기 그래프

1	1	0	-1
0	0	-1	1
0	0	-1	0

 

1일 경과 후

1	1	2	-1
2	2	-1	1
0	0	-1	2

 

2일 경과 후

1	1	2	-1
2	2	-1	1
3	3	-1	2

 

bfs종료

 

from collections import deque

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

def tomato():
  
  while q:
    x,y = q.popleft()

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      #인접한 좌표가 범위 조건을 만족하고 토마토가 아직 안 익었을 경우
      if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0:
        graph[nx][ny]=graph[x][y]+1
        q.append((nx,ny))
  return


#입력받기
  
m,n = map(int,input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int,input().split())))

#이미 익어있는 토마토 좌표를 큐에 넣는다
q = deque()
for i in range(n):
  for j in range(m):
    if graph[i][j]==1:
      q.append((i,j))
      
#bfs수행
tomato()

#정답 출력
ans=0
for i in range(n):
  for j in range(m):
    #안 익은 토마토가 하나라도 존재하면 -1을 출력하고 종료
    if graph[i][j] == 0:
      print(-1)
      exit(0)
    if graph[i][j]>ans:
      ans = graph[i][j]

print(ans-1)