[백준/DFS-BFS] 7576: 토마토 - 파이썬

문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

풀이

bfs를 이용하여 익은 토마도가 며칠이 지나면 모든 토마토를 다 익는지 구하는 문제다.

먼저 그래프를 돌면서 토마토가 있는 좌표를 큐에 넣고 bfs로 하나씩 pop하면서 토마토가 있는(문제에서는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

graph[3][5] = 1, graph[0][0] 이면 해당좌표 (0,0), (3,5)를 큐에 넣는다.

(0,0)을 pop하고 상하좌우로 토마토가 있는부분(0인부분)의 좌표를 큐에넣고 (이때 큐는 (3,5), (1,0))이 있다.

주변 토마토가 있는 좌표의 원소값을 1 증가시킨다. 

 

마찬가지로 (3,5)를 pop하고 (2,5)를 큐에 넣고 해당 좌표의 원소값을 1증가시킨다. 

이렇게 반복하면 그래프에서 가장 큰 원소값이 마지막으로 익은 토마토이며 이때 모든 토마토가 익게되므로

해당 원소값이 문제에서 구하고자 하는 값이다. 

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

graph = []
queue = deque([])
m, n = map(int, input().split())

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i,j])

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

def bfs():
    while queue:
        x, y = queue.popleft()

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

            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append([nx,ny])

bfs()
result = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(-1)
            exit(0)
        result = max(result, graph[i][j])

print(result - 1)