[백준] 7576번: 토마토 - python

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

7576번: 토마토

 

아이디어

 

토마토가 있는 곳을 찾아서 그 부분부터 BFS를 진행하여 나머지 토마토를 찾아 여행을 떠난다.

그 과정에서 토마토의 자리에 전에 있었던 값을 계속해서 더해 나가면서 상자 전체를 탐험한다.

그 후에 만약 토마토가 안익은 자리가 있으면 -1을 하면서 break를 걸어주고 아니라면 최대값을 찾아 출력해준다.

 

약간 응용 BFS이긴 했지만  아래 부분을 사용하여 경로 길이를 계산하는 로직만 짠다면 쉽게 풀 수 있는 문제인 것 같다.

arr[nx][ny] = arr[x][y] + 1

 

from collections import deque
m, n = map(int, input().split())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

dq = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
s = 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            dq.append((i, j))
            
while dq:
    x, y = dq.popleft()
    for k in range(4):
        nx = dx[k] + x
        ny = dy[k] + y
        

        if 0<=nx<n and 0<=ny<m:
            if arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] + 1
                dq.append((nx, ny))
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            print(-1)   
            exit()     
print(max(map(max,arr))-1)

 

완성