백준 7576 문제 풀이 python

🐒 토마토

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

✍ 나의 풀이

from collections import deque



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


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

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx,ny))
        

matrix = []
for _ in range(n):
    matrix.append(list(map(int, input().split())))

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

bfs()
result = 0
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    result = max(result, max(i))
print(result - 1)

이전 문제와 유사하지만 bfs 큐의 사용이 약간 다르다.

🧠 문제 이해

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

예제에 위와같은 입력이 주어지는데,
만일 DFS알고리즘을 사용한다면 문제에서 요구하는 답을 출력하기 어려울 것이다.

BFS에서는 먼저 익은 토마토인 1을 탐색을해서 (1,1)과 (6,4)를 queue에 append 하고 bfs를 실행할 수 있다. 양쪽 끝에서 출발한 토마토가 중앙에서 만난다.

1, -1,  7,  6,  5, 4
2, -1,  6,  5,  4, 3
3,  4,  5,  6, -1, 2
4,  5,  6,  7, -1, 1