썩은 오렌지 문제
You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.
체크해야할 점
- BFS 로 풀어야 한다.
- 썩은 오렌지가 많을 수 있다.
BFS
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
from collections import deque
queue = deque()
visited = set()
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0
# 처음 시작할 썩은 오렌지 위치 파악
for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 2: ### 썩은 토마토 일때 상하좌우로 다 일단 해주자
queue.append((row, col, answer))
visited.add((row, col))
while queue:
x, y, answer = queue.popleft()
for i in range(4):
tmp_x = x + dx[i]
tmp_y = y + dy[i]
if tmp_x >= 0 and tmp_x < len(grid) and tmp_y >= 0 and tmp_y < len(grid[0]):
if grid[tmp_x][tmp_y] == 1 and (tmp_x, tmp_y) not in visited:
grid[tmp_x][tmp_y] = 2
queue.append((tmp_x, tmp_y, answer+1))
visited.add((tmp_x, tmp_y))
for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 1:
return -1
else:
return answer
