[DFS/BFS] 백준 - 7576번 토마토

7576번 토마토

👏 문제 요약

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.

😊 key point

전형적인 bfs, dfs 문제이다. 만약 graph가 0이 아니라면 무시를 하고 만약 0이라면 이동하려고 하는 노드 = 이동하기 전 노드의 + 1을 해준다.

😉 코드

from collections import deque

n,m = map(int, input().split())

graph = []

for _ in range(m):
    graph.append(list(map(int, input().split())))

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

q = deque()

# 익은 토마토를 찾아 q에 넣는다. 
for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            q.append((i,j))

count = [0]

def bfs():

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            if graph[ny][nx] != 0:
                continue
            
            # 이동 조건
            if graph[ny][nx] == 0:
                
                graph[ny][nx] = graph[y][x] + 1
                q.append((ny,nx))

def check():
    for i in range(m):
        for j in range(n):
            if graph[i][j] == 0:

                return -1              #0값이 있다면 -1
                
    return max(map(max,graph)) -1      #graph에서 최대값을 추출

bfs()

print(check())