[DFS/BFS] 7576-토마토

링크 - 토마토

문제점

처음에 1을 찾고 탐색을 시작하는 부분에서 어려움을 겪었다.

만약 창고에 익은 토마토가 1개라면 문제가 없지만 익은 토마토의 개수가 2개 이상이라면 탐색 순서를 어떻게 해야할지 고민을 했었다.

해결방법!

BFS를 사용하면 해결할 수 있었다.
먼저 익은 토마토의 위치를 큐에 저장을 해놓으면 여러 군데에서 퍼져나가는 형식으로 탐색을 할 수 있었다.

+) 익는 날짜를 세는 방법은 미로탈출 문제에서 썼던 방식을 사용했다.
(map에 바로 바로 숫자를 더해가며 표기하는 방식)

코드

from collections import deque
M,N = map(int, input().split())

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

count=0
tomato=[]
queue= deque()
def bfs():
    while queue:
        x,y = queue.popleft()
        
        for k in range(len(dx)):
            nx = x+dx[k]
            ny = y+dy[k]
            if nx>=0 and nx<N and ny>=0 and ny<M:
                if tomato[nx][ny]==0:
                    tomato[nx][ny]= tomato[x][y]+1
                    queue.append([nx,ny])
                    
    return tomato

#토마토 맵 입력받기
for i in range(N):
    line = list(map(int,input().split()))
    tomato.append(line)
    for idx,t in enumerate(line):
        if t==1:
            queue.append([i,idx]) #익은 토마토의 위치를 저장


tomato = bfs()

answer=0

#토마토 탐색
for line in tomato:
    for t in line:
        if t == 0:
            print(-1)
            exit(0)
        else:
            answer = max(answer,t)
            
print(answer-1)