[BFS] 백준 7576 토마토 설명 (python)

BFS를 가장 잘 보여주는 대표적인 문제라고 생각됩니다.

 

문제는 아래와 같습니다.

토마토 밭이 주어지고 그중 1로 표시된 곳은 익은 토마토가 있고, 0으로 표시된 곳은 익지 않은 토마토가 있습니다.

하루가 지날때마다 익은 토마토 상.하.좌.우의 토마토가 익게 됩니다.

주어진 토마토밭의 토마토가 모두 익는 데까지 걸리는 일자를 구하는 문제입니다.

 

위의 그림에서 1일의 좌측상단에 1로 표시된 곳이 익은 토마토가 있는 곳이고 문제의 설명과 같이 상하좌우로 점점 익으며 7일에 모두 익게 됩니다.

 

BFS에서 사용되는 큐와 함께 보면 더 이해가 쉽게 됩니다.

현재 익은 토마토의 좌표를 큐에 넣어주는 작업을 먼저 합니다.

이후 큐에서 하나씩 꺼내 상.하.좌.우를 살펴 익지 않은 토마토가 있다면 해당 좌표를 큐에 넣어줍니다.

[0,0] 기준으로 아래와 같이 검사합니다.

상 [0,-1] = 범위 벗어남

하 [0,1] = 익지 않은 토마토

좌 [-1,0] = 범위 벗어남

우 [1,0] = 익지 않은 토마토

 

익지 않은 토마토의 좌표를 큐에 넣어주고 다시 작업을 진행합니다.

[0,1] 기준으로 아래와 같이 검사하고 익지 않은 토마토의 좌표를 큐에 넣어 줍니다.

상 [0,0]= 익은 토마토

하 [0,2]= 익지 않은 토마토 큐에 추가

좌 [-1,1]= 범위 벗어남

우 [1,1] = 익지 않은 토마토 큐에 추가

 

[1,0] 기준으로 동일한 작업을 반복합니다.

 

바둑판 모양의 배열이 주어진 BFS문제에서는 이러한 순서로 해결합니다.

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().strip().split())

graph = [list(map(int, input().split())) for _ in range(N)]
    
queue = deque([])

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

for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            queue.append([i,j])


def bfs():
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = dx[i]+x, dy[i]+y
            if 0<=nx<N and 0<=ny<M and graph[nx][ny]==0:
                graph[nx][ny]= graph[x][y]+1
                queue.append([nx,ny])
                
bfs()
res=0
for i in graph:
    for j in i:
        if j==0:
            print (-1)
            exit(0)
    res = max(res, max(i))

print (res-1)

위의 소스코드에서 dx,dy는 상.하.좌.우로 이동을 위한 배열을 선언한 것입니다.

처음 이중 for문을 통해 토마토 밭에서 익은 토마토의 값이 있다면 queue에 추가합니다.

bfs에서 그림으로 설명한 것과 같이 상.하.좌.우를 살피며

(if문) 범위 안에 속하고 익지 않은 토마토 라면 값을 변경하고 큐에 추가합니다.

마지막 for문에서는 최대로 걸린 날짜를 구하고 만약 없다면 -1을 출력합니다.