994. Rotting Oranges (Medium)

994. Rotting Oranges

 

쉬운 bfs 문제

백준 토마토들을 열심히 풀었다면 10분컷할 수 있다

연결된 오렌지 군집에 여러 썩은 오렌지가 있는 경우만 조심해서 큐에 미리 넣어주면 된다

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n,m = len(grid), len(grid[0])
        v = [[-1]*m for _ in range(n)]

        dirx, diry=[0,0,-1,1],[-1,1,0,0]
        q = deque()

        for i in range(n):
            for j in range(m):
                # 썩은 오렌지
                if grid[i][j]==2:   
                    q.append((j, i))
                    v[i][j] = 0
        

        while q:
                cx, cy = q.popleft()
                for dx, dy in zip(dirx, diry):
                    nx, ny = cx+dx, cy+dy
                    if 0<=nx<m and 0<=ny<n and grid[ny][nx]==1 and v[ny][nx]==-1:
                        q.append((nx,ny))
                        v[ny][nx] = v[cy][cx]+1

        res = 0
        
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:
                    if v[i][j]==-1:
                        return -1
                    res = max(res, v[i][j])
        
        return res