[Python] 백준 7576번 : 토마토

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

7576번: 토마토

---

💡 문제 풀이

BFS 문제이다.

 

BFS를 돌면서 가장 경우를 따져서 찾아내면 된다.

다 돌았는데 0이 있다면 -1을 출력하고 종료하면 되고

아니라면 가장 큰 값을 찾아서 출력하는데 1로 시작했으니 1을 빼줘야 한다.

✔️ 느낀 점

이번에 BFS/DFS를 구현하면서 많이 익숙해진 것 같다. 큰 틀 자체는 어렵지 않고 이제 어떤 방식으로

도출해 나갈지에 대해서만 생각을 하면될 것 같다. 이것도 조금의 연습만 있으면 될 것 같다.

💻 코드

from collections import deque
import sys

m, n = map(int, sys.stdin.readline().split())
matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
queue = deque([])
moves = [(-1,0), (1,0), (0,-1), (0,1)]
res = 0

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

def BFS():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = moves[i] + x, moves[i] + y
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

BFS()
for i in matrix:
    if 0 in matrix[i]:
        print(-1)
        sys.exit(0)
    res = max(res, max(i))
print(res - 1)