토마토

문제 분석

굉장히 기본적인 BFS 문제였다.

deque를 활용해 point들을 쌓아놓고, 먼저 들어온 point들 부터 다시 네 방향으로 탐색해준다. 이때, 갈 수 없는곳 혹은 이미 방문한 곳은 제외하고 탐색하면 된다.

예제 입력 2번 처럼 -1들에 막혀 더이상 익지 못하는 토마토가 존재하는 경우를 주의해야 한다.

While 문을 돌 때, 우리가 point를 저장한 deque가 더 이상 탐색할 곳이 없어 빈 리스트가 되면, 탐색을 종료한다. 이때, 탐색을 종료했는데도 0인 tomato가 남아있으면 위와 같은 상황으로 인지하고, -1을 출력해주면 된다.


CODE

import sys
read=sys.stdin.readline
from collections import deque

n,m=map(int,read().split())
tomato=list(list(map(int,read().split())) for _ in range(m))

check=list(list(-1 for _ in range(n)) for _ in range(m))#며칠만에 익는지 저장
point=deque([])#탐색해야 할 point 저장

for i in range(m):
    for j in range(n):
        if tomato[i][j]==1:
            point.append([i,j])
            #1인 점에서 익기 시작함으로 point에 추가
            check[i][j]=0
            #1인 점은 0일째에 익어있음으로 check를 0으로 변경

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

while point:
    a,b=point.popleft()
    for x,y in zip(dx,dy):
        ax=a+x
        by=b+y
        if 0<=ax<m and 0<=by<n and tomato[ax][by]==0:
            if check[ax][by]==-1: check[ax][by]=check[a][b]+1
            else:check[ax][by]=min(check[ax][by],check[a][b]+1)
            tomato[ax][by]=1
            point.append([ax,by])

for aa in tomato:
    if 0 in aa:
    #point들을 모두 돌았는데도 0이 남아있으면
    #막혀서 갈 수 없는 영역이 존재한다는 뜻임으로 -1출력
        print(-1)
        sys.exit()

answer=0
for i in range(m): answer=max(answer,max(check[i]))
print(answer)



While 문 마지막에 tomato안에 0이 있는지 없는지 확인해 0이 남아있는 경우와 0이 없는 경우를 구별하는 식으로 코드를 짰다. 하지만, 이렇게 되면 while문을 돌때마다 tomato를 탐색하게 됨으로 시간복잡도가 굉장히 증가한다. 이 문제인지 모르고 계속 시간초과로 고생했다..

while point:

    ~~~
    ~~~

    if all(0 not in aa for aa in tomato):
        flag=2
        break

2020-10-17 이제까지 DP문제들은 비교적 많이 풀었으니까 DFS/BFS를 집중적으로 해봐야겠다고 어제에 이어 느꼈다.

  • 아기상어
  • 스타트 택시

‘아기상어’와 ‘스타트 택시’도 토마토 문제와 비슷한데, 거리가 가까운, 좌상단의 먹이 부터 먹어야 한다는 조건을 아직 만족시키지 못하고 있다.(거의 다 했는데)

2주간 BFS/DFS문제들을 집중적으로 다뤄볼 예정이다.


[다시 풀어보기]