What is the best way to solve Rotting Oranges?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

썩어가는 오렌지

'썩어가는 오렌지' 문제에 대한 자세한 가이드 및 Python 구현.

문제 설명

쉬움

각 셀이 세 가지 값 중 하나를 가질 수 있는 m x n 그리드가 제공됩니다.

- 0은 빈 셀을 나타냅니다.

- 신선한 오렌지를 나타내는 1, 또는

- 2는 썩은 오렌지를 나타냅니다.

1분마다 썩은 오렌지와 4방향으로 인접한 신선한 오렌지는 모두 썩습니다.

어떤 셀에도 신선한 오렌지가 없을 때까지 경과해야 하는 최소 시간(분)을 반환합니다. 이것이 불가능하다면 -1을 반환합니다.

orangesRotting(grid: List[List[int]]) -> int 함수를 작성하세요.

제약

•m == len(grid)
•n == len(grid[i])
•1 <= m, n <= 10
•grid[i][j] is 0, 1, or 2

예

Example 1

Input

grid = [[2,1,1],[1,1,0],[0,1,1]]

Output

Explanation

Minute 0: rotten at (0,0). Fresh at (0,1), (0,2), (1,0), (1,1), (2,1), (2,2). Minute 1: fresh at (0,1) and (1,0) rot. Minute 2: fresh at (0,2) and (1,1) rot. Minute 3: fresh at (2,1) rot. Minute 4: fresh at (2,2) rot.

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 adjacent to a rotten orange, so it stays fresh.

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

from collections import deque
def oranges_rotting_opt(grid):
    q = deque()
    time, fresh = 0, 0
    ROWS, COLS = len(grid), len(grid[0])
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1: fresh += 1
            if grid[r][c] == 2: q.append((r, c))
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while q and fresh > 0:
        for i in range(len(q)):
            r, c = q.popleft()
            for dr, dc in directions:
                row, col = r + dr, c + dc
                if 0 <= row < ROWS and 0 <= col < COLS and grid[row][col] == 1:
                    grid[row][col] = 2
                    q.append((row, col))
                    fresh -= 1
        time += 1
    return time if fresh == 0 else -1

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def oranges_rotting_brute(grid):
    rows, cols = len(grid), len(grid[0])
    time = 0
    while True:
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                            to_rot.append((nr, nc))
        if not to_rot: break
        for r, c in to_rot: grid[r][c] = 2
        time += 1
    for row in grid:
        if 1 in row: return -1
    return time