[Python] 백준 7576 : 토마토

BFS로 푸는 기본적인 문제 중에 하나인 토마토 문제를 풀어보았습니다.

 

 

 

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

7576번: 토마토

 

저의 풀이는 5가지로 나눴습니다.

1. 맵과 n,m을 입력받는다.

2. 토마토가 있는 1의 지점을 받고 queue에 저장한다.

3. bfs에 넣어서 queue에서 pop 해주어 동서남북으로 탐색 후 0을 발견하면 지금 자리에 +1을 하여 맵에 업데이트 후 queue에 해당 좌표를 넣어준다.

4. queue가 비게 될 경우까지 반복을 한다.

5. 맵에서 0이 있으면 -1을 출력하고, 맵에서 가장 큰 숫자를 뽑아주고 -1을 하여 출력하여준다.

 

 

from collections import deque
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
res = 0
queue = deque()

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 = dx[i] + x, dy[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:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)

 

이상입니다!