[백준] 7576 토마토 - BFS

jckim22·2023년 7월 25일

BFS 백준 알고리즘

[ALGORITHM] STUDY (PS)

목록 보기

44/86

난이도

Gold 5

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력

6

문제 검토

넓은 범위로 한 바퀴 도는 것을 하루로 치기 때문에 DFS가 아닌 BFS가 적절한 알고리즘이 되겠다.

풀이(python)

Python - 첫 풀이

from collections import deque
m,n=map(int,input().split())
stage=[list(map(int,input().split())) for _ in range(n)]
res=0
def bfs():
    global res
    q=deque()
    #처음 스테이지에서 익은 토마토의 좌표를 큐에 넣어준다
    for x in range(n):
        for y in range(m):
            if stage[x][y]==1:
                q.append([x,y]) 
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]        
    while q:
        arr=[]
        #큐에 들어있는 좌표들을 배열에 append 해준다.
        for i in range(len(q)):
            x,y=q.popleft()    
            arr.append([x,y])
        #배열에 들어 있는 모든 좌표들로 bfs진행
        #한 턴이 끝나면 한 depth가 끝난 것이므로 count+1
        for i in arr:
            x,y=i[0],i[1]            
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx<0 or nx>=n or ny<0 or ny>=m:
                    continue
                if stage[nx][ny]==1 or stage[nx][ny]==-1:
                    continue
                stage[nx][ny]=1
                q.append([nx,ny])        
        res+=1
bfs()
#만약 bfs를 거치고도 익지 않은 토마토가 있다면 -1을 출력
for x in range(n):
    for y in range(m):
        if stage[x][y]==0:
            print(-1)
            exit()
print(res-1)

이 풀이에서는 하루를 잡아야하기 때문에 한 바퀴 돌고 q에 있는 좌표를 임시 배열에 넣고 그 배열에 있는 좌표들로 또 한 바퀴 돌리면서 카운트하며 문제를 풀었다.

정답을 얻었지만 큰 메모리와 시간을 소요했다.

문제를 풀고 생각이 들었는데 한 칸씩 갈 때마다 1이 증가한다면 그냥 가중치가 똑같을 때 최단 경로를 구하는 문제랑 다를게 없다는 것이다.

그래서 이전에 최단경로 문제를 풀 듯이 stage에 depth를 누적시켜 저장해서 문제를 풀었다.

아래는 그 풀이이다.

Python - 최단경로 풀이

from collections import deque
m,n=map(int,input().split())
stage=[list(map(int,input().split())) for _ in range(n)]
def bfs():
   q=deque()
   #처음 스테이지에서 익은 토마토의 좌표를 큐에 넣어준다
   for x in range(n):
       for y in range(m):
           if stage[x][y]==1:
               q.append([x,y]) 
   dx=[-1,1,0,0]
   dy=[0,0,-1,1]        
   while q:
       x,y=q.popleft()            
       for i in range(4):
           nx=x+dx[i]
           ny=y+dy[i]
           if nx<0 or nx>=n or ny<0 or ny>=m:
               continue
           if stage[nx][ny]>=1 or stage[nx][ny]==-1:
               continue
           #depth를 저장
           stage[nx][ny]=stage[x][y]+1
           q.append([nx,ny])                
bfs()
res=0
for x in stage:
   for y in x:
       if y==0:
           print(-1)
           exit()
   res=max(res,max(x))
print(res-1)