[Python] 백준 알고리즘 7576번 - 토마토

[Python] 백준 알고리즘 7576번 - 토마토

 

문제 출처 : https://www.acmicpc.net/problem/7576

7576번: 토마토

접근 방식

전형적인 그래프 너비 탐색(BFS) 문제이다. 

문제에서 요하는 지점, 익은 토마토(1)인 지점에서 각자 0 인 지점을 찾아가며 탐색을 하는 문제이다.  

1에서 시작한 탐색은 상하좌우로 탐색을 하며 0인 지점을 찾고 체크하고 넘어간다. 

다른 BFS 기본문제와의 차이점은 기본적인 BFS문제는 시작점이 하나였지만 토마토와 같은 문제는 시작점이 여러 개여서

해당 시작점들을 먼저 큐에 넣어주고 시작해야 한다는 점이다

 

1이 여러 개이면 여러 군데에서 동시에 토마토가 익는다는 것을 생각하고 코드를 작성해야 한다. 

 

 풀이 코드 

# 7576 / 토마토
from collections import deque

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

# 이동을 위한 방향
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 리스트 생성
num = []
for i in range(n):
    num.append(list(map(int, input().split())))

queue = deque()

# BFS
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 and num[nx][ny] == 0:
                num[nx][ny] = num[x][y] + 1
                queue.append((nx, ny))


for i in range(n):
    for j in range(m):
        if num[i][j] == 1:
            queue.append((i, j))

BFS()

max = 0
for i in range(n):
    for j in range(m):
        if max < num[i][j]:
            max = num[i][j]
        elif num[i][j] == 0:
            max = -1
            break
    if max == -1:
        break

if max == -1:
    print(max)
else:
    print(max - 1)